⚡Flashcard Drill➔
NeetCode #334LC-92MediumLinked ListNC 250
← Back to All Problems

#334 · #92 · Reverse Linked List II(反转链表 II)

📌 Problem Statement & Constraints

Given the head of a linked list and two integers left and right with left <= right, reverse the nodes from position left to position right and return the list. Constraints: 1 <= n <= 500, 1 <= left <= right <= n.

💡 Core Algorithmic Approaches

  1. Walk to the node just before position left (call it prev), then repeatedly move the node after cur to the front of the sublist.
  2. Each of the right - left iterations moves one node from the tail of the sublist to its head, which reverses the sublist in place.
  3. The dummy head handles left == 1 without a special case.
  4. This is the "head insertion" reversal technique and is more compact than reversing and reconnecting.

💻 Benchmark Python3 Implementation

class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        prev = dummy
        for _ in range(left - 1):          # node before the sublist
            prev = prev.next
        cur = prev.next                    # first node of the sublist
        for _ in range(right - left):
            tmp = cur.next                 # node to move to the front
            cur.next = tmp.next
            tmp.next = prev.next
            prev.next = tmp
        return dummy.next

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass over the list.
💾 Space Complexity
O(1): the reversal is done by relinking.

⚠️ Interview Pitfalls & Follow-ups

  • Iterating right - left + 1 times: that would move one node too many. The count is right - left.
  • Forgetting the dummy head: left == 1 would need a separate branch.
  • Losing the sublist head: cur stays at the original first node of the sublist throughout, which is correct -- it becomes the sublist's tail.
  • Confusing prev.next with cur: the insertion point is always prev.next, the current front of the sublist.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Linked List Problems