Problem

Reverse a linked list from position m to n. Do it in-place and in one-pass.

OR

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.

Examples

Example 1:

---
title: Input
---
 
 graph LR
   A1[1] --> B2[2]:::reversed --> C3[3]:::reversed --> D4[4]:::reversed --> E5[5]
 
   classDef reversed fill:#ffcc00,stroke:#000,stroke-width:2px;
  
---
title: Output
---
 
 graph LR
   A1[1] --> D4[4]:::reversed --> C3[3]:::reversed --> B2[2]:::reversed --> E5[5]
 
   classDef reversed fill:#ffcc00,stroke:#000,stroke-width:2px;
  
1
2

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

Example 2:

1
2

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

Note:

Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.

Note 2:

Usually the version often seen in the interviews is reversing the whole linked list which is obviously an easier version of this question.

Solution

Method 1 - Iteration

Here is the approach:

  1. Initialization:
    • Use a dummy node to handle edge cases where the reversal might include the head node.
    • Use pointers to keep track of the node just before the reverse segment and the end of the reverse segment.
  2. Move to Start of Reversal Segment:
    • Move a pointer to the left-1 position.
  3. Reverse the Segment:
    • Reverse the nodes between left and right.
  4. Reconnect the Links:
    • Reconnect the reversed segment back into the original list.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
	public ListNode reverseBetween(ListNode head, int left, int right) {
	    if (head == null || left == right)
	        return head;
	
	    ListNode dummy = new ListNode(0);
	    dummy.next = head;
	    ListNode prev = dummy;
	
	    // Move prev to the node before the left position
	    for (int i = 0; i < left - 1; i++) {
	        prev = prev.next;
	    }
	
	    ListNode start = prev.next;
	    ListNode then = start.next;
	
	    // Reverse the sublist using insertion technique
	    for (int i = 0; i < right - left; i++) {
	        start.next = then.next;
	        then.next = prev.next;
	        prev.next = then;
	        then = start.next;
	    }
	
	    return dummy.next;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        if not head or left == right:
            return head

        dummy = ListNode(0)
        dummy.next = head
        prev = dummy

        # Move prev to the node before the left position
        for _ in range(left - 1):
            prev = prev.next

        start = prev.next
        then = start.next

        # Reverse the sublist using insertion technique
        for _ in range(right - left):
            start.next = then.next
            then.next = prev.next
            prev.next = then
            then = start.next

        return dummy.next

Complexity

  • ⏰ Time complexity: O(n) , where n is the number of nodes in the linked list. Each node is processed at most twice.
  • 🧺 Space complexity: O(1), as we only use a constant amount of extra space for pointers.