⚡Flashcard Drill➔
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

  1. Compute the length n and locate the tail, then reduce k modulo n.
  2. Make the list circular by linking the tail to the head.
  3. The new tail is at index n - k - 1; the new head is its successor.
  4. Sever the circle at the new tail. This is O(n) regardless of how large k is.

💻 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: k can 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 - 1 steps from the head, so the loop runs n - k - 1 times.
  • Not breaking the circle: the list would be infinite.
  • Handling k == 0 after 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.
🎯 Drill This Card Now➔

🧩 Related Linked List Problems