LL-k reverse doubt

#1

Please tell me the problem in my code?

#2

hi @56amrut.bhokardankar i tried to dry run your code but it too complex and you are using a lot of pointers, even if one pointer is being used at any point where it cannot be used (usually in situations where lets say ptr = NULL and we try to access ptr->next) runtime errors arise. I am attaching a simpler approach, please have a look.

Algorithm :

  1. Reverse the first sub-list of size k.
    1.1 While reversing keep track of the next node and previous node.
    1.2 Let the pointer to the next node be next and pointer to the previous node be prev.
  2. head->next = reverse(next, k) /* Recursively call for rest of the list and link the two sub-lists */
  3. return prev /* prev becomes the new head of the list */
Node reverse(Node head, int k)
    { 

       Node current = head; 
       Node next = null; 
       Node prev = null; 

       int count = 0; 

       /* Reverse first k nodes of linked list */
       while (count < k && current != null)  
       { 
           next = current.next; 
           current.next = prev; 
           prev = current; 
           current = next; 
           count++; 
       } 

       /* next is now a pointer to (k+1)th node  
          Recursively call for the list starting from current. 
          And make rest of the list as next of first node */
       if (next != null)  
          head.next = reverse(next, k); 

       // prev is now head of input list 
       return prev; 
}
1 Like