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
- Walk to the node just before position
left(call itprev), then repeatedly move the node aftercurto the front of the sublist. - Each of the
right - leftiterations moves one node from the tail of the sublist to its head, which reverses the sublist in place. - The dummy head handles
left == 1without a special case. - 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 + 1times: that would move one node too many. The count isright - left. - Forgetting the dummy head:
left == 1would need a separate branch. - Losing the sublist head:
curstays at the original first node of the sublist throughout, which is correct -- it becomes the sublist's tail. - Confusing
prev.nextwithcur: the insertion point is alwaysprev.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.