NeetCode #333LC-61MediumLinked List
← Back to All Problems#333 · #61 · Rotate List(旋转链表)
📌 Problem Statement & Constraints
Given the head of a linked list, rotate it to the right by
k places and return the head. Constraints: the number of nodes is in [0, 500], -100 <= Node.val <= 100, 0 <= k <= 2 * 10^9.💡 Core Algorithmic Approaches
- Compute the length
nand locate the tail, then reducekmodulon. - Make the list circular by linking the tail to the head.
- The new tail is at index
n - k - 1; the new head is its successor. - Sever the circle at the new tail. This is O(n) regardless of how large
kis.
💻 Benchmark Python3 Implementation
class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if not head or not head.next:
return head # 0 or 1 node -> unchanged
# find the length and the tail
n = 1
tail = head
while tail.next:
tail = tail.next
n += 1
k %= n # k can be huge
if k == 0:
return head
tail.next = head # make it circular
# the new tail is n - k - 1 steps from the head
new_tail = head
for _ in range(n - k - 1):
new_tail = new_tail.next
new_head = new_tail.next
new_tail.next = None # break the circle
return new_head⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): one pass to find the length and one to locate the new tail.
💾 Space Complexity
O(1): pointer manipulation only.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting
k %= n:kcan be up to 2 * 10^9, so the loop bound would be astronomically large. - Off-by-one on the new tail index: it is
n - k - 1steps from the head, so the loop runsn - k - 1times. - Not breaking the circle: the list would be infinite.
- Handling
k == 0after the modulo: the circular linking would still work, but the early return avoids needless work.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.