Leetcode 92: Reverse Linked List II#

🧠 Problem Description#

Given the head of a singly linked list and two integers left and right, reverse the nodes of the list from position left to position right, and return the reversed list.

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

🔧 Solution Idea: Head Insertion Method#

✅ Steps:#

Create a dummy node dummy to simplify edge cases (like reversing from the head).
Move pre to the node right before position left.
Set curr = pre.next to point to the start of the sublist to be reversed.
Perform right - left head insertions, where each node after curr is inserted right after pre.

🔁 Core Loop Explanation#

curr = pre.next
for _ in range(right - left):
    temp = curr.next         # ① Get the node after curr
    curr.next = temp.next    # ② Detach temp from its current position
    temp.next = pre.next     # ③ Point temp to the front of the reversed part
    pre.next = temp          # ④ Insert temp after pre

✅ Example of Insertion:#

Initial list: 1 → 2 → 3 → 4 → 5, reverse positions 2~4
After operations: 1 → 4 → 3 → 2 → 5

📌 Head Insertion Technique Summary#

The head insertion method is a common linked list technique especially useful for partial reversals. The core idea is:

“Take the next node after curr and insert it right after pre, repeatedly.”

🎯 Typical Use Cases:#

Reversing a sublist
Insertion sort on linked list

✅ Full Python Code#

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        dummy = ListNode(0)
        dummy.next = head
        pre = dummy

        for _ in range(left - 1):
            pre = pre.next

        curr = pre.next
        for _ in range(right - left):
            temp = curr.next
            curr.next = temp.next
            temp.next = pre.next
            pre.next = temp

        return dummy.next

🔚 Summary#

This problem demonstrates the powerful “head insertion” technique for in-place linked list reversal within a specified range. It is a classic and elegant approach to mastering linked list manipulation.