Reversing in between a linked list

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]

Following is my code :

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

}

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;

}

if( second == null ){

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

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

else {

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

}
i++;
}
}

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 ?

• What does reverse the nodes mean? Reale reverse the references, or just values? Feb 17, 2023 at 22:14
• You might be interested in this question. Jul 18, 2023 at 15:28

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):

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

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):

v
(1 -> (2 -> ...))

(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):

v
(1 -> (2 -> ...))
^

(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
// points to node before reversed portion, may stay null
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) {
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;