DSA sheet · Linked List · Reversal pattern (circular list idea)

Rotate List

This problem sits in the reversal section of the sheet, but the teacher points out straight away that no reversing is needed. The real tool is a circular linked list: join the tail to the head to make a ring, then cut the ring at the right place. Before that, she teaches an important habit: when k can be huge (up to 2·10⁹) but the list is tiny (≤ 500 nodes), use modulo to throw away the useless full rotations. She also shows a brute force that copies the values into arrays, so we can see why the in-place version is better.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Brute force: copy values, rotate in an array, write back
• Part B · Optimal: make a ring, then cut it (in place)
• Part C · Revision page

Part 0 · Before starting

Linked list basics

A linked list is a chain of nodes. Each node has a val and a next pointer to the node after it. The last node (the tail) has next = None. We are given the first node, the head.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

[1] → [2] → [3] → [4] → [5] → None
 ↑                         ↑
head                      tail

• Walking: curr = head, then curr = curr.next repeatedly. Each such move is a jump.
• No index access: to reach the i-th node you must jump i times from head, O(n). There's no going backwards.
• Keep head safe: walk with copies; head still points at the old first node until we decide otherwise.
• Save next before changing a pointer: before you overwrite node.next, make sure whatever it pointed to is saved somewhere (or still reachable), or that part of the list is lost. In Part B we save the new head before cutting the link that leads to it.

Circular linked list

If the tail's next points back to head instead of None, the chain becomes a ring: you can walk round forever. There's no "first" or "last" node in a ring. You choose where it starts by where you cut it.

[1] → [2] → [3] → [4] → [5]
 ↑                         │
 └─────────────────────────┘     (tail.next = head)

Modulo (%)

a % b is the remainder when a is divided by b. Example: 6 % 5 = 1, 11 % 5 = 1, 16 % 5 = 1, 10 % 5 = 0. It's the tool for "going round in circles": after every b steps you are back where you started, so only the remainder matters.

Part A · Brute force: copy values, rotate in an array, write back

LeetCode 61

1The question in simple words

You get the head of a linked list and a number k. Rotate the list to the right by k places and return the new head. One rotation means: take the last node off and put it at the front.

start:         [1] → [2] → [3] → [4] → [5] → None
1 rotation:    [5] → [1] → [2] → [3] → [4] → None
2 rotations:   [4] → [5] → [1] → [2] → [3] → None    ← answer for k = 2

2What the constraints tell us

• Number of nodes: 0 to 500 → the list can be empty. We need a base case: if head is None, return None. A single node also never changes when rotated.
• 500 nodes is small, and linked-list solutions are linear anyway, so the list size can't cause TLE (that starts around 10⁸ operations, and is certain around 10⁹).
• k can be up to 2·10⁹. That's the interesting part. If we did one rotation at a time, k = 2·10⁹ rotations would surely TLE. But with only 500 nodes, most of those rotations are pointless (see the next step). Huge k + small n means: use modulo.

3Intuition: rotations go round in a circle

The teacher rotates 1 2 3 4 5 six times:

After n rotations (n = length) the list is exactly as it was. So k = 1, 6, 11, 16 … all give the same answer as k = 1, because 6 % 5 = 11 % 5 = 16 % 5 = 1. Only k % n rotations really matter. After this, k is at most n − 1 ≤ 499, tiny.

And if k % n == 0 (k is a multiple of the length, e.g. 5 rotations of 5 nodes), nothing changes at all: return head as it is.

4Building the logic: the array formula

The teacher reuses the array-rotation idea from the arrays topic. Copy the values into a Python list, rotate them into a second list, and write them back into the nodes.

Where does each value go after k right rotations? The value at index i moves k places to the right. If that runs off the end, it wraps round to the front. So:

Example: vals = [1, 2, 3, 4, 5], k = 2, n = 5:

Then walk the list again and overwrite each node's value from rotated: the first node gets 4, then 5, 1, 2, 3. Return the same head.

5Approach steps

1. If head is None or head.next is None → return head (nothing to rotate).
2. Walk the list and copy every value into vals. n = len(vals).
3. k = k % n. If k is 0 → return head.
4. Make rotated of size n; for each i: rotated[(i + k) % n] = vals[i].
5. Walk the list again, writing rotated[0], rotated[1], … into the nodes.
6. Return head.

6Code (Python)

class Solution:
    def rotateRight(self, head, k):
        if head is None or head.next is None:   # 0 or 1 node
            return head

        vals = []
        curr = head
        while curr is not None:                 # copy values out
            vals.append(curr.val)
            curr = curr.next

        n = len(vals)
        k = k % n                               # drop full circles
        if k == 0:
            return head

        rotated = [0] * n
        for i in range(n):
            rotated[(i + k) % n] = vals[i]      # move each value k to the right

        curr = head
        i = 0
        while curr is not None:                 # write values back
            curr.val = rotated[i]
            i += 1
            curr = curr.next
        return head

7Code line by line

8Dry run

1 → 2 → 3 → 4 → 5, k = 2.

k = 7 on the same list gives 7 % 5 = 2, the same answer. k = 5 gives 0 → the list is returned untouched.

9Complexity & remember

• Time O(3n) = O(n): one pass to copy, one to fill rotated, one to write back. (With n ≤ 500, that's at most about 1500 steps, still fast.)
• Space O(2n) = O(n): the two extra lists, vals and rotated.

Part B · Optimal: make a ring, then cut it (in place)

1The question (same as Part A)

Same input and output, but now we want to rearrange the nodes themselves, with no extra arrays: O(1) extra space.

2What the constraints tell us

• Still need the base case for 0 or 1 node (and k = 0 changes nothing either).
• Still need k % length because k can be 2·10⁹. That means we must find the length first, which costs one pass.

3Intuition: a necklace

Look at the answer for k = 2: 4 5 1 2 3. It's the same order as 1 2 3 4 5 if you read it round a circle, just starting from 4. So:

1. Join the tail (5) to the head (1). Now it's a necklace: 1 2 3 4 5 1 2 3 …
2. Cut the necklace just before 4. The piece starts at 4 and ends at 3: 4 → 5 → 1 → 2 → 3 → None.

Only two pointers change: the old tail's next (5 → 1) and the new tail's next (3 → None). The teacher says when you see it, you'll be amazed how simple it is.

4Building the logic from examples

Step 1: find the length and the tail in one walk

Start curr on head with length = 1 (we are already standing on one node). Move while curr.next is not None, adding 1 each time. When the loop stops, curr is on the tail and length is the true count.

Step 2: shrink k, and stop early if nothing changes

k = k % length. With 5 nodes and k = 2 (or 7, or 2·10⁹ + 2…), k becomes the real number of rotations. If it is 0, return head right away.

Step 3: join tail to head

curr.next = head. curr is on 5, so 5 now points to 1. The pointer head itself still sits on 1; we haven't moved it.

Step 4: how many jumps to the new tail? length − k − 1

After k right rotations, the last k nodes move to the front. So the new head is the node at position length − k (counting from 0), and the new tail is the one just before it.

• length = 5, k = 2: steps = 5 − 2 = 3, the new head is node 4 (index 3). The new tail is node 3, which is 2 jumps from head (1 → 2 → 3) = 5 − 2 − 1 ✓.
• The teacher writes the loop as "i from 1 while i < steps", which runs steps − 1 times. That's the same length − k − 1 jumps.

Step 5: save the new head, then cut

Standing on the new tail (3): new_head = new_tail.next (that's 4), then new_tail.next = None. Return new_head.

5Approach steps

1. If head is None, or head.next is None, or k == 0 → return head.
2. Walk to the tail, counting nodes (start length at 1).
3. k %= length; if k == 0 → return head.
4. tail.next = head (make a ring).
5. From head, take length − k − 1 jumps → this is the new tail.
6. new_head = new_tail.next, then new_tail.next = None. Return new_head.

6Code (Python)

class Solution:
    def rotateRight(self, head, k):
        if head is None or head.next is None or k == 0:
            return head

        curr = head
        length = 1                       # we're standing on head already
        while curr.next is not None:     # stop ON the tail
            curr = curr.next
            length += 1

        k = k % length
        if k == 0:                       # full circles only: no change
            return head

        curr.next = head                 # tail -> head: a ring

        new_tail = head
        for _ in range(length - k - 1):  # walk to the node before the new head
            new_tail = new_tail.next

        new_head = new_tail.next         # save it before cutting
        new_tail.next = None             # cut the ring
        return new_head

7Code line by line

8Dry run

1 → 2 → 3 → 4 → 5, k = 2.

after step 1 (found the tail):
[1] → [2] → [3] → [4] → [5] → None
 ↑                         ↑
head                      curr

after step 3 (ring made):
[1] → [2] → [3] → [4] → [5]
 ↑                         │
 └─────────────────────────┘

after step 5 (standing before the new head):
[1] → [2] → [3] → [4] → [5]
 ↑           ↑     ↑       │
 │      new_tail  new_head │
 └─────────────────────────┘

after step 6 (cut):
[4] → [5] → [1] → [2] → [3] → None
 ↑                         ↑
new_head               new_tail

Other cases

• k = 1: 5 − 1 − 1 = 3 jumps → new tail 4, new head 5 → 5 1 2 3 4 ✓.
• k = 4 = n − 1: 0 jumps → new tail is head (1), new head 2 → 2 3 4 5 1 ✓.
• k = 5 = n or k = 10: k % 5 = 0 → return head unchanged ✓.
• k = 2·10⁹ + 2: k % 5 = 2 (because 2·10⁹ is a multiple of 5) → same as k = 2 ✓.
• [0, 1, 2], k = 4 (LeetCode example 2): length 3, k = 1 → 1 jump → new tail 1, new head 2 → 2 0 1 ✓.
• Empty list / one node: base case, returned as is ✓.

9Complexity & remember

• Time O(2n) = O(n): one pass to find the length and tail, then length − k − 1 more jumps. That's close to n in the worst case (when k is small, like 1). Linear overall.
• Space O(1): just a few pointer and number variables. No arrays, and the nodes themselves are rearranged (truly in place).

Part C · Revision page

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build(values):
    dummy = ListNode()
    tail = dummy
    for v in values:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

s = Solution()
print(to_list(s.rotateRight(build([1, 2, 3, 4, 5]), 2)))       # [4, 5, 1, 2, 3]
print(to_list(s.rotateRight(build([0, 1, 2]), 4)))             # [2, 0, 1]
print(to_list(s.rotateRight(build([1, 2, 3, 4, 5]), 5)))       # [1, 2, 3, 4, 5]
print(to_list(s.rotateRight(build([1, 2, 3, 4, 5]), 2 * 10**9 + 2)))  # [4, 5, 1, 2, 3]
print(to_list(s.rotateRight(build([]), 3)))                    # []

Based on this video: Rotate List | Circular Linked List