Reverse Linked List II (One pass)


  • 0
    M

    It's simple Linked List reversal but the part reversed list should be included of the existing one.

    Visual Solution for the Sample Input:
    0_1507593337619_18e19c73-b278-497e-ac40-694f329489c8-image.png

    Only the edge cases would be if m=1 (i.e first node), n = length(Linkedlist)

    In the above example if m=1 n = 5 then we get a completely reversed list.

    Spoiler
    Key: All we do apart from linked list reversing is to save pointers of the parent (node just before head of list reversal and node before that : parentPrev).
    Also a counter which keeps track of the node location using an index i (starting from 1).

      public static ListNode reverseBetween(ListNode head, int m, int n) {
          int i=1; 
          ListNode prev = null, curr=head, next=null;
          while(i!=m) { prev = curr; curr = curr.next; i++;}
          ListNode parent = curr, parentPrev = prev; 
          while(curr!=null && i<=n){ // regular reverse list with i<=n as extra condition
              next = curr.next;
              curr.next = prev;
              prev = curr;
              curr = next;
              i++;
          }
          if(parentPrev!= null) { 
              parentPrev.next = prev;
              parent.next = next;
              return head;
          }else{ // m ==1 reverse from start
            parent.next = curr;
            return prev;
          }
      }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.