Solution: Reverse Linked List II

Statement

Given a singly linked list with $n$ nodes and two positions, left and right, the objective is to reverse the nodes of the list from left to right. Return the modified list.

Constraints:

• $1 \leq$ n $\leq 500$
• $-5000 \leq$ node.data $\leq 5000$
• $1 \leq$ left $\leq$ right $\leq$ n

Solution

So far, you’ve probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which to follow based on considerations such as time complexity and implementation constraints.

Naive approach

The naive approach uses two pointers left and right to keep track of the sublist and reverse it. The pointers left and right are intialized to the head of the linked list.

We begin by moving the left pointer to the $m^{th}$ node, that represents the start of the sublist and the right pointer to the $n^{th}$ node, that represents the end of the sublist. Next, while the left pointer is behind the right pointer, we take the following steps:

1. We swap the values of the nodes pointed to by the left and the right pointer.

2. We move the left pointer one step forward to the $(m + 1)^{th}$ node.

3. Since we are given a singly linked list, and there is no prev, we can’t update the right pointer in the same way as we did for the left pointer, i.e., moving it backward to the $(n-1)^{th}$ node. Instead, on each iteration, we reset the right pointer to the head of the list and then move it forward to the $(n-1)^{th}$ node.

4. We repeat steps 1–3 until both pointers meet at some point, or the right crosses left.

The time complexity of this solution is $O(n^2)$, since we’re swapping the nodes, and traversing the list per iteration. The space complexity of this solution $O(1)$, since we use a constant number of extra variables.