Microsoft Jane Street Interview Question
Software Engineer / DevelopersAbove code skips last element, following is the working with little modification
void LinkedList::Reverse(Node* root, Node* prev)
{
if(root->next == NULL)
{
this->list = root;
this->list->next = prev;
return;
}
Reverse(root->next, root);
root->next = prev;
}
// Simple Solution without confusion
/* Let j be pointer to 1st node of list then initial call ll be list_rec_reverse(&j, NULL, j) */
void list_rec_reverse(list **l, list *prev, list *curr)
{
if(NULL == curr)
{
*l=prev;
return;
}
list_rec_reverse(l,curr,curr->next);
curr->next = prev;
}
1) use a recursive function that provides sublist tail as result (and updates head as side-effect)
2) use two references to adjacent nodes (current and previous), chain current.next to previous
public class ReverseLinkedList {
private class Node {
private int value;
private Node next;
public Node(int value){
this.value = value;
}
public int getValue(){ return value;}
public Node getNext(){ return next;}
public void setNext(Node next){ this.next = next;}
}
private Node head;
public ReverseLinkedList(){
}
public void add(int v){
Node n = new Node(v);
n.setNext(head);
head = n;
}
public int remove(){
if( null == head){
throw new IllegalStateException("can't remove from empty list");
}
int v = head.getValue();
head = head.getNext();
return v;
}
public void reverse(){
if( null != head ){
Node newTail = reverseSubList(head);
newTail.setNext(null);
}
}
public void reverse2(){
if( null != head ){
Node previous = head;
Node n = head.getNext();
head.setNext(null);
while( null != n ){
Node oldNext = n.getNext();
n.setNext(previous);
previous = n;
n = oldNext;
}
head = previous;
}
}
public void print(){
Node n = head;
while( null != n ){
System.out.print(n.getValue());
System.out.print(" -> ");
n = n.getNext();
}
System.out.print("null");
}
// n is sublist head
// return sublist tail once reversed
// updates head reference when needed
private Node reverseSubList(Node n){
if( null == n.getNext()){
head = n;
} else {
Node subListTail = reverseSubList(n.getNext());
subListTail.setNext(n);
}
return n;
}
public static void main(String[] args){
ReverseLinkedList list = new ReverseLinkedList();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.print();
list.reverse();
list.print();
list.reverse2();
list.print();
}
}
public class node
{
public object data;
public node next;
public node()
{
data = null;
next = null;
}
public node(object item)
{
data = item;
next = null;
}
}
public class LinkList
{
private node List;
public int count=0;
public LinkList()
{
List = null;
}
public void AddNode(object item)
{
if (List == null)
{
List = new node(item);
count++;
}
else
{
node temp = new node(item);
node p = List;
while (p.next != null)
{
p = p.next;
}
p.next = temp;
count++;
if (count%1000 == 0)
Console.WriteLine(count);
}
}
public void Revese()
{
node cur, prev=null, l;
if (List !=null)
l = List;
else
return;
while (l != null)
{
cur = l;
l = l.next;
cur.next = prev;
prev = cur;
}
List = prev;
}
}
C# version reverse linked list using recursion
Node reverseRecurse(Node prev, Node cur)
{
if(cur==null) return cur;
Node head;
//recursion first
if(cur.next!=null)
head=reverseRecurse(cur,cur.next);
else
head=cur;
//revert pointer
cur.next=prev;
//handle last level recursion
return head;
}
main()
{
Node list;
list = reverseRecurse(null, list);
}
If there are no restrictions on memory usage, you can use an external stack.
func reverseLinkedList(Node *head)
Node temp = head
while (temp!= NULL)
Stack.push(temp->data)
temp=temp->next;
//Now pop the elements back. you have it in the reverse order
while(Stack.isEmpty)
Node node
if(!head)
head = node
head->next = NULL
else
node->data = pop()
node->next = head
head = node
return head
I haven't done error correction, but the iterative code would be some what like above.
You can also have a recursive version in a similar fashion.
void reverse_LL(*root, *head)
{
if(root == NULL || root->next == NULL)
{
head = root;
return;
}
if(root->next->next == NULL)
{
head = root->next;
root->next->next = root;
root->next = NULL;
return;
}
reverse(root->next, head);
root->next->next = root;
root->next = NULL;
return;
}
I don't think "if(root->next->next == NULL)" is necessary, since you already considered when root->next == NULL.
so the code would be:
void reverse_LL(*root, *head)
{
if(root == NULL || root->next == NULL)
{
head = root;
return;
}
reverse(root->next, head);
root->next->next = root;
root->next = NULL;
}
the version by euv921, modify to,
// root is the original head, head is the new head of the list.
void reverse_LL(Node ** root, Node** head)
{
if(root == NULL || (*root)->next == NULL)
{
*head = *root;
return;
}
reverse_LL(&(*root)->next, head);
(*root)->next->next = *root;
(*root)->next = NULL;
};
help other engineers to save time ......
// my version, works, //
void reverseList( Node ** pphead)
{ if(!*pphead) return;
Node * tmp;
Node* current;
Node * result = NULL;
current = *pphead;
while(current)
{ tmp = current->next;
current->next = result;
result = current;
current = tmp; }
*pphead = result;
};
void reverseListRecur( Node ** pphead)
{ if(!pphead||!*pphead||!(*pphead)->next) return;
Node * first = *pphead;
Node* rest = first->next;
reverseListRecur(&rest);
first->next->next = first;
first->next = NULL;
*pphead = rest;
};
It would mostly work... I hope ;)
node* reverse(node* head)
{
node* temp;
if(!head) // If empty list, empty list would be the result
return NULL;
if(!head->next) // If it is a single node or last node,
return head; //it would again be the reversed one
temp = reverse(head->next); // Reverse the remaining part of the list
head -> next -> next = head; // Come back, and reverse the link between the nodes
head -> next = NULL; // This is just a case for the head of the list
return temp; // Returns the head of the reversed linked list
}
//Create a class Node
public class Node {
String key;
public String getKey() {
return key;
}
public void setKey(String key) {
this.key = key;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
Node next ;
}
//Create a Singly Linked List
public class LinkedList {
Node HEAD;
Node TAIL;
public LinkedList(Node HEAD,Node TAIL) {
this.HEAD = HEAD;
this.TAIL = TAIL;
}
public void traveseList(){
Node n = this.HEAD;
while(n != null){
System.out.println("Value at Node::" + n.getKey());
n = n.getNext();
}
}
public void reverseList(){
Node n,n1,n2;
n = this.HEAD;
n1 = n.getNext();
n2 = n1.getNext();
this.TAIL = n;
n.setNext(null);
while(n1.getNext() != null){
n1.setNext(n);
n = n1;
n1 = n2;
n2 = n2.getNext();
}
n1.setNext(n);
this.HEAD = n1;
}
public static void main(String[] args) {
Node n1 = new Node();
Node n2 = new Node();
Node n3 = new Node();
Node n4 = new Node();
Node n5 = new Node();
Node n6 = new Node();
n1.setKey("JAVA");
n2.setKey("RUBY");
n3.setKey("HTML");
n4.setKey("C++");
n5.setKey("C");
n6.setKey("Obj C");
n1.setNext(n2);
n2.setNext(n3);
n3.setNext(n4);
n4.setNext(n5);
n5.setNext(n6);
n6.setNext(null);
LinkedList list = new LinkedList(n1, n6);
list.traveseList();
list.reverseList(); // Reverse the list
System.out.println("Revers List...");
list.traveseList();
}
}
node *rev(node *root)
{
node *rev = NULL;
node *temp = root;
while (temp){
node *current = temp->next;
temp->next = rev;
rev = temp;
temp = current;
}
return rev;
}
node *rev(node *root)
{
if (!root)
return NULL;
node *head = rev(root->next);
root->next->next = root;
root->next = NULL;
return head;
}
node *rev(node *root)
{
node *rev = NULL;
node *temp = root;
while (temp){
node *current = temp->next;
temp->next = rev;
rev = temp;
temp = current;
}
return rev;
}
node *rev(node *root)
{
if (!root)
return NULL;
node *head = rev(root->next);
root->next->next = root;
root->next = NULL;
return head;
}
Solution:
public void ReverseList()
{
Node loop = Head;
Node reverse = null;
Node temp = null;
Console.Clear();
Console.WriteLine("\nOriginal List.....");
DisplayList();
while (loop != null)
{
temp = loop.Next;
loop.Next = reverse;
reverse = loop;
loop = temp;
}
Head = reverse;
Console.WriteLine("\nReversed List....");
DisplayList();
}
- S February 21, 2011