link mingle home | logged in as: guest | login/register| submit link


IndiaDiscuss.com : Social Bookmarkings and News Networking Site for India
interview_questions
Bookmarks
Reversing a Linked List
14
Votes

Reverse a Link List using Recursion

saved under Amazon Interview Questions by interview_questions

  
reverse (Node headNode){
 if(headNode.next==null)return headNode;
 Node rev = reverse(headNode.next);
 Node t = rev;
 while(t.next()!=null)t=t.next;
 t.next = headNode;
 headNode.next = null;
 return rev;
}

comment by search on 2008-06-27 02:40:55
void rev(node *now, node *pre){ node *sec, *th; if( !now )return; sec = now -> link; if(sec)th = sec -> link; else th = 0; now -> link = pre; if(sec)sec -> link = now; if(!th){if(sec)first = sec;else first = now;} rev(th, sec); }
comment by gaurav1987pal on 2009-12-26 04:09:45
public class LinkedListClient { public static void main(String args[]) { int arr[] = { 1, 2, 5, 3, 4 }; Node head = LinkedListHelper.createList(arr); LinkedListHelper.printList(head); head = LinkedListHelper.reverseList(head); LinkedListHelper.printList(head); } } class Node { int value; Node next; public Node(int value) { this.value = value; } } class LinkedListHelper { public static Node createList(int[] arr) { Node head = null, temp = null, prev = null; for (int i = 0; i < arr.length; i++) { temp = new Node(arr[i]); if (i == 0) { head = temp; prev = temp; } else { prev.next = temp; prev = prev.next; } } return head; } public static void printList(Node head) { Node iterator = head; while (iterator != null) { System.out.println(":" + iterator.value); iterator = iterator.next; } } public static Node reverseList(Node head) { Node thisNode = head; Node oldHead = head; myReverse(oldHead, thisNode); return newHead; } private static Node newHead; private static Node myReverse(Node oldHead, Node thisNode) { if (thisNode.next == null) { newHead = thisNode; return thisNode; } Node nextNode = myReverse(oldHead, thisNode.next); nextNode.next = thisNode; if (thisNode == oldHead) { thisNode.next = null; return null; } return thisNode; } }
comment by anshusharma1983 on 2010-01-27 10:05:12
call the below method as reverse(head,null) reverse(head,prev){ if( head == null) return prev; temp = head.next; head.next = prev; return reverse(temp,head); }
comment by aravinds03 on 2010-09-25 15:39:10
 



Enter the string above
 
IndiaDiscuss | Published News | Hot
Indian Social News and Links Network
IndiaDiscuss | Published News
Indian Social News and Links Network