Reversing in between a linked list

Question

I have written code for this leetcode problem :-

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list. For example :

Input: head = [1,2,3,4,5], left = 2, right = 4 Output: [1,4,3,2,5]

Link of the problem

Following is my code :

 public ListNode reverseBetween(ListNode head, int left, int right) {

        if(head == null || head.next == null) {
            return head;
        }

        ListNode first = head;
        ListNode second = head.next;
        ListNode prev = head;

        int i = 1;

        while( second != null ) {

            ListNode nxt = second.next;

            if( i == left ) {

                ListNode temp = first;

                while( i < right ) {

                    second.next = first;
                    first = second;
                    second = nxt;

                    if( nxt == null ) {
                        break;
                    }

                    nxt = second.next;
                    i++;
                }

                if( left == 1 ){

                    temp.next = second;
                    head = first;
                    return head;

                }

                if( second == null ){

                    prev.next = first;
                    temp.next = null;
                    return head;
                }

                prev.next = first;
                temp.next = second;
                return head;
            }

            else {

                prev = first;
                first = second;
                second = nxt; 

            }
            i++;
        }
        return head;
    }

Although it works, I feel like it is not good enough and can be improved. Any suggestions for any kind of improvements that can be made ?

Answer 1

The code is fine and I cannot find a testcase that breaks it. It is a bit hard to follow with nested blocks: you iterate using an index and depending on that index you compute other things in loops. Maybe it could be better to split the work into sequential blocks.

First, let's change the example and have left be 3 instead of 2

^{(this makes the example part of the most general case, otherwise some pointers are aliased)}

For this problem you have three sections:

1. Iterate the list until you find the first node part of the reversed subset, and keep track of the leading node (predecessor of first):

    head
    v
    (1 -> (2 -> (3 -> (4 -> (5 -> null)))))
          ^     ^
          |     first
          leading
   

2. Reverse in place the section. While you have nodes to process, keep track of the last visited node and point back to it. Be careful about the order of operations. back is null initially, and you point to the current item with cursor:

          next
          v
    (3 -> (4 -> (5 -> null)))
    ^cursor
   
    back is null
   

   After one step:

          next
          v
    (4 -> (5 -> null))
    ^cursor
   
    (3 -> null)
    ^back 
   

   After another step:

          next
          v
    (5 -> null)
    ^cursor
   
    (4 -> (3 -> null))
    ^back 
   

3. You link leading to the last computed value for back, e.g. you make 2 point to 4, and you link the first node to you current cursor, e.g. you link 3 to 5. There are cases when there is no such leading node, if the left index is 1, in which case you cannot return head: you need to return back instead.

   No-prefix case (assume start is 1):

    head
    v
    (1 -> (2 -> ...))
    leading is null
   
    (5 -> null)
    ^cursor
   
    (4 -> (3 -> (2 -> (1 -> null))))
    ^back             ^first
   

   In this case, just attach cursor as a tail of first. The return value is back.

   General case (assume start is 3):

    head
    v
    (1 -> (2 -> ...))
          ^     
          leading
   
    (5 -> null)
    ^cursor
   
    (4 -> (3 -> null))
    ^back ^first
   

   Make cursor the tail of first (same as before), and back the tail of leading. The return value is head.

Here is a C++ version that assumes the list is not null and the indices satisfy their constraints.

    ListNode* reverseBetween(ListNode* head, int left, int right) {

        /* Declarations */

        // used to iterate down the list
        ListNode* cursor = head;
        // points to node before reversed portion, may stay null
        ListNode* leading = nullptr;
        // link to previous node
        ListNode* back = nullptr;
        // first node in original list that belongs to reversed section
        ListNode* first = nullptr;

        /* Switch to 0-based indices for simplicity */

        left--;
        right--;

        /* Find starting node, keeping track of the node before it. */

        // may never run (left is first item)
        while (left > 0) {
            leading = cursor;            
            cursor = cursor->next;
            left--;
            right--;
        }
        // this is the head of the list to reverse
        first = cursor;

        /* reverse the sublist in place */

        // right index is inclusive so use ">="
        while (right >= 0) {
            ListNode* next = cursor->next;
            cursor->next = back;
            back = cursor;
            right--;
            cursor = next;
        }

        /* tie all parts together */

        // put the rest of the list to the tail of the first reversed node
        first->next = cursor;

        if (leading != nullptr) {
            // there is a prefix list, attach it to the 
            // head of the reversed portion
            leading->next = back;
            // return the original pointer, the prefix list
            return head;
        } else {
            // return the head of the reversed subsection
            return back;
        }
    }

Answer 2

This solution looks really complicated, since normaly it should be left<=right. In this case you first have to find the left node and then the right one. The simplest solution is just using for loops to get to the coresponding nodes. Also error handling seems to be mising for example when right<left or one or both values are out of bounds.