01/11/2017

[Java] Reverse singly linked list

Here is a simple algorithm to reverse a singly linked list in O(N) time and O(1) space. The only tricky part is the correct handling of the pointers :)

The idea is to start with a previous pointer to null and a pointer to the head of the list, then:

1) track the next element in a temporary variable
2) reverse the current element pointer
3) consider the current element as the previous for next iteration
4) move the current element to the next one to handle
5) when no more elements are left to be processed, the previous pointer will be the new list head

 //reverse singly linked list  
 public static SingleLinkedListNode reverseList(SingleLinkedListNode head){  
   if(head == null) return head;  
   
   SingleLinkedListNode prev = null, next, curr = head;  
   
   /*  
   1) track next element  
   2) reverse current element pointer  
   3) track current element as previous for next iteration  
   4) move current element to the next one to handle  
   */  
   while (curr != null) {  
     next = curr.next;  
     curr.next = prev;  
     prev = curr;  
     curr = next;  
   }  
   
   //at this time this will point to the beginning of the reversed list!  
   return prev;  
 }  


You can check more singly and doubly linked lists utilities on my Gist along with some test cases in SingleLinkedListJTests.

No comments:

Post a Comment

With great power comes great responsibility.

Da grandi poteri derivano grandi responsabilità.