LeetCode Solutions Blog

Reverse Linked List II

Number: 92

Difficulty: Medium

Paid? No

Problem Description

Given the head of a singly linked list and two integers left and right (with left <= right), reverse the nodes of the list from position left to right and return the modified list. For example, for head = [1,2,3,4,5], left = 2 and right = 4, the output is [1,4,3,2,5].

Key Insights

Use a dummy node to simplify edge cases.
Traverse the list to locate the node immediately before the reversal section.
Reverse the sublist in-place by adjusting pointers iteratively.
Reconnect the reversed sublist back to the original list.
Achieve the reversal in one pass through the list.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The solution uses an in-place reversal technique. A dummy node is created to handle cases where the reversal starts at the head. First, traverse to the node immediately before the left-th node. Then, reverse the sublist by iteratively moving the next node in the sublist to the front of the reversed portion. Finally, reconnect the reversed section with the remainder of the list. The key trick here is the iterative reversal within the sublist which ensures that the overall reversal is done in a single pass with constant extra space.

Code Solutions

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
        # Create a dummy node that points to the head to simplify edge cases.
        dummy = ListNode(0)
        dummy.next = head
        # Initialize pointer 'prev' to the dummy node.
        prev = dummy
        # Move 'prev' to the node immediately before the left-th node.
        for i in range(left - 1):
            prev = prev.next
        # 'curr' will point to the first node of the sublist to be reversed.
        curr = prev.next
        # Reverse the sublist from left to right.
        for i in range(right - left):
            temp = curr.next          # 'temp' is the node to be moved.
            curr.next = temp.next     # Bypass 'temp' in the current sublist.
            temp.next = prev.next     # Insert 'temp' right after 'prev'.
            prev.next = temp          # Update 'prev' to point to the moved node.
        # Return the new head, which is dummy.next.
        return dummy.next