11/04/2017

[Java] Reverse doubly linked list

Here is a O(N) time and O(1) space method to reverse a doubly linked list:

 //reverse doubly linked list  
   public static DoubleLinkedListNode reverseList(DoubleLinkedListNode head){  
     if(head == null) return head;  
   
     DoubleLinkedListNode prev = null;  
   
     while(head != null){  
       DoubleLinkedListNode next = head.next;  
       head.next = prev;  
       prev = head;  
       head = next;  
     }  
   
     return prev;  
   }  


You can check the implementation on my Gist along with the definition of the DoubleLinkedList class and some test cases.

No comments:

Post a Comment

With great power comes great responsibility.

Da grandi poteri derivano grandi responsabilità.