Solution: Reverse Linked List II

Let's solve the Reverse Linked List II problem using the In-Place Manipulation of a Linked List pattern.

We'll cover the following

Statement

Given a singly linked list with nn 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≤1 \leq n ≤500\leq 500
  • −5000≤-5000 \leq node.data ≤5000\leq 5000
  • 1≤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 mthm^{th} node, that represents the start of the sublist and the right pointer to the nthn^{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(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(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(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(n2)O(n^2), since we’re swapping the nodes, and traversing the list per iteration. The space complexity of this solution O(1)O(1), since we use a constant number of extra variables.

Optimized approach using in-place manipulation of a linked list

The essence of this algorithm lies in refining the process of reversing specific sublists within a linked list by directly adjusting the pointer of the nodes, ensuring efficient in-place manipulation without using additional memory. It begins with the initialization of a dummy node, placed before the head of the list, to simplify edge cases, such as sublist reversals starting from the first node of the list. The algorithm starts by linking the dummy node to the head of the list and iterating the list until reaching the node immediately preceding the sublist to be reversed, marking it as the previous node. Then, for each node in the sublist, it moves that node to the front of the sublist and connects it to the previous node, effectively reversing its order and seamlessly integrating the reversed sublist back into the main list. The algorithm returns the dummy next as the head of the newly reversed linked list.

Now, let’s look at this algorithm in detail:

This optimized approach directly modifies the pointers of the nodes within the linked list. It achieves this by carefully tracking the sublist’s current, next, and previous nodes within the sublist to be reversed.

The algorithm steps are given below:

  • We initialize a dummy node, which will be helpful in scenarios where the reversal of the sublist starts from the head of the list.

  • We set the next node of dummy to point to the head of the list.

  • We initialize a pointer, prev, to the dummy node. This pointer will help us reconnect the sublist to the entire list after it has been reversed.

  • We use a loop to traverse the list with the prev pointer and until it reaches the node immediately before the sublist to be reversed.

  • We initialize a curr pointer, which points to the node next to prev.

  • Another loop is used to reverse the sublist. This loop iterates right - left times, which is the number of nodes in the sublist minus one:

    • We set next_node to curr.next, representing the node to be moved to the front of the reversed sublist.
    • We update curr.next to next_node.next, effectively removing next_node from its current position in the sublist.
    • We set next_node.next to prev.next, inserting next_node at the beginning of the reversed sublist.
    • We update prev.next to next_node, adjusting the pointer to next_node for the next iteration.

  • Finally, we return dummy.next, which is the head of the modified linked list.

The slides below illustrate how the algorithm runs:

Press + to interact
canvasAnimation-image
1 of 12

Let’s look at the code for this solution below:

Solution.java
LinkedListNode.java
LinkedList.java
PrintList.java
class Solution {
    // Function to reverse the sublist within the linked list
    public static LinkedListNode reverseBetween(LinkedListNode head, int left, int right) {
        
        if (head == null || left == right) {
            return head;
        }
        LinkedListNode dummy = new LinkedListNode(0);
        dummy.next = head;
        LinkedListNode prev = dummy;
        for (int i = 0; i < left - 1; i++) {
            prev = prev.next;
        }
        LinkedListNode curr = prev.next;
        for (int i = 0; i < right - left; i++) {
            LinkedListNode nextNode = curr.next;
            curr.next = nextNode.next;
            nextNode.next = prev.next;
            prev.next = nextNode;
        }
        return dummy.next;
    }
    // Driver Code
    public static void main(String[] args) {
        int[][] input = {
            {1, 2, 3, 4, 5, 6, 7},
            {6, 9, 3, 10, 7, 4, 6},
            {6, 9, 3, 4},
            {6, 2, 3, 6, 9},
            {6, 2}
        };
        int[] left = {1, 3, 2, 1, 1};
        int[] right = {5, 6, 4, 3, 2};
        for(int i=0; i<input.length; i++){
            System.out.print(i+1);
            LinkedList<Integer> list = new LinkedList<Integer>();
            list.createLinkedList(input[i]);
            System.out.print(".\tOriginal linked list:  ");
            PrintList.printListWithForwardArrow(list.head);
            System.out.print("\tLeft: " + left[i] + ", Right: " + right[i] + "\n\n");
            System.out.print("\tReversed linked list:  " );
            PrintList.printListWithForwardArrow(reverseBetween(list.head,left[i],right[i]));
            System.out.println(PrintHyphens.repeat("-", 100));
        }
    }
}
Reverse Linked List II

Solution summary

To recap, the solution to this problem can be divided into the following five main steps:

  • We initialize a dummy node and link it to the head of the linked list.

  • We locate the node preceding the sublist to be reversed by traversing the list.

  • We set a pointer to the starting node of the sublist to be reversed.

  • Within a loop, we iteratively reverse the sublist by adjusting pointers, moving one node at a time.

  • We return the head of the reversed sublist, ensuring the original list remains intact.

Time complexity

The time complexity of this solution is O(n)O(n), where nn is the number of nodes in the linked list. This is because each node will be processed at most one time.

Space complexity

The space complexity of this solution is O(1)O(1), since we are using a constant number of additional variables to maintain the connections between the nodes during the reversal process.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.