Reverse Linked List II

medium LeetCode #92
linked-list

Description

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.

Note: Positions are 1-indexed.

Example 1:
Input: head = [1, 2, 3, 4, 5], left = 2, right = 4
Output: [1, 4, 3, 2, 5]
Explanation: Nodes at positions 2, 3, 4 have values 2, 3, 4. After reversing: 1 -> 4 -> 3 -> 2 -> 5.

Example 2:
Input: head = [5], left = 1, right = 1
Output: [5]
Explanation: Single node, reversing position 1 to 1 results in no change.

Example 3:
Input: head = [1, 2, 3], left = 1, right = 3
Output: [3, 2, 1]
Explanation: Reverse the entire list.

Constraints

  • The number of nodes in the list is n
  • 1 <= n <= 500
  • −500 <= Node.val <= 500
  • 1 <= left <= right <= n

Complexity

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

Hints

Show Hints
Pattern
In-place linked list reversal with boundary tracking
Approach
Use a dummy node, find the node before 'left', then reverse the sublist in-place by repeatedly moving nodes to the front of the reversed section
Complexity
Single pass with pointer manipulation

Solutions

Show PY Solution 
from typing import Optional


class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def solution(head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
    # single loop
    dummy = ListNode(-1)
    dummy.next = head

    curr = dummy
    i = 0
    pre_left = None
    start = None
    while i < right:
        i += 1
        if i < left:
            curr = curr.next
        elif i == left:
            pre_left = curr
            start = curr.next
        else:
            temp = start.next
            # print("temp", temp.val, "pre_left", pre_left.val, "start", start.val)
            start.next = temp.next
            temp.next = pre_left.next
            pre_left.next = temp

    # print(pre_left.val, start.val, dummy.next.val)

    # curr = dummy.next
    # while curr:
    #     print(curr.val, end=' ')
    #     curr = curr.next

    return dummy.next

    # with dummy
    #
    # dummy = ListNode(-1)
    # dummy.next = head
    #
    # pre_left = dummy
    # start = None
    # for i in range(left - 1):
    #     pre_left = pre_left.next
    #
    # start = pre_left.next
    #
    # i = 0
    # n = right - left + 1
    #
    # prev = None
    # curr = start
    # while curr and i < n:
    #     next_node = curr.next
    #     curr.next = prev
    #     prev = curr
    #     curr = next_node
    #     i += 1
    #
    # pre_left.next = prev
    # start.next = curr
    #
    # return dummy.next

    # without dummy
    #
    # i = 0
    # n = head
    # start = None
    # pre_start = None
    # while n:
    #     i += 1
    #     if left - 1 == i:
    #         pre_start = n
    #     if left == i:
    #         start = n
    #
    #     n = n.next
    #
    # i = 0
    # n = right - left + 1
    #
    # prev = None
    # curr = start
    # while curr and i < n:
    #     next_node = curr.next
    #     curr.next = prev
    #     prev = curr
    #     curr = next_node
    #     i += 1
    #
    # if pre_start:
    #     pre_start.next = prev
    # else:
    #     head = prev
    # start.next = curr
    #
    # return head