Rotate and swap nodes in pairs

Why it matters

Rotation is a common pattern in real programs. A round-robin scheduler moves the job that just ran to the back of the queue, and a playlist moves the first track to the end. Swapping pairs is a classic interview question. It looks simple, but one wrong pointer assignment loses part of the list, so the steps have to happen in the right order.

Both tasks change only the next fields of existing nodes. Neither one creates a new node, so the work is pointer editing and nothing else. The basics lesson in this module covers how a node holds the address of the next node, and this lesson assumes that.

Part 1: rotate right by k

What rotate means

Rotating right by 1 moves the last node to the front. Rotating right by 2 does that twice. Take the list 1 -> 2 -> 3 -> 4 -> 5:

• Rotate right by 1: the 5 moves to the front, giving 5 -> 1 -> 2 -> 3 -> 4.
• Rotate right by 2: the 4 moves to the front, giving 4 -> 5 -> 1 -> 2 -> 3.

The answer for rotating by 2 is 4 -> 5 -> 1 -> 2 -> 3. The last two nodes moved to the front, and the others kept their order.

A useful way to picture this is a ring. Join the tail back to the head, and the five nodes form a circle with no start and no end. Rotating means choosing a new place to cut the ring. For rotate right by 2, cut the circle between 3 and 4, and 4 becomes the new head. Cutting in that spot gives 4 -> 5 -> 1 -> 2 -> 3.

Why only k modulo n matters

Let n be the number of nodes. Rotating right by n steps brings every node back to where it started, so the list is unchanged. The same is true for any multiple of n. So only the remainder matters.

The remainder, also called the modulo, is what is left after dividing. In C++ the operator is %. For a list of 5 nodes, 7 % 5 is 2, so rotating by 7 gives the same result as rotating by 2. Rotating by 5 gives 5 % 5, which is 0, so the list does not change.

This is why the code takes k % n first. Without it, a large k makes the cut point fall off the list, and the program gives a wrong answer without any error message. The mistakes section shows that result.

Finding the new tail

After the remainder shift is known, the new tail is the node shift places before the old tail. Number the nodes from the head, starting at 0. For a list of n nodes, the new tail is at index n - shift - 1, and the new head is the node after it, at index n - shift.

Check this with 1 -> 2 -> 3 -> 4 -> 5 and shift of 2:

• n - shift - 1 is 5 - 2 - 1, which is 2. Index 2 holds the value 3, so 3 is the new tail.
• n - shift is 3. Index 3 holds the value 4, so 4 is the new head.

The rotate code

The function first finds the tail and counts the nodes. Then it does the steps from the ring picture: close the ring, walk to the new tail, cut the ring, and return the new head.

Node* rotate_right(Node* head, int k) {
    if (head == nullptr || head->next == nullptr) return head;
 
    int n = 1;
    Node* tail = head;
    while (tail->next != nullptr) {
        tail = tail->next;
        ++n;
    }
 
    int shift = k % n;
    if (shift == 0) return head;
 
    tail->next = head;                 // close the chain into a loop
    int steps = n - shift - 1;         // nodes to walk past before the new tail
    Node* new_tail = head;
    for (int i = 0; i < steps; ++i) {
        new_tail = new_tail->next;
    }
    Node* new_head = new_tail->next;
    new_tail->next = nullptr;          // cut the loop
    return new_head;
}

The first line handles two cases: an empty list and a list with one node. Rotating either of them changes nothing, so the function returns the head as it is. The shift == 0 line handles any k that is a multiple of n, which also changes nothing.

The order of the last steps matters. tail->next = head closes the ring first. The walk stops before it reaches the old tail's link, so it never goes around the ring. new_tail->next = nullptr must come after new_head is saved, because cutting the link first would lose the pointer to the new head.

Worked example 2: rotate by 7

Take 1 -> 2 -> 3 -> 4 -> 5 and k of 7.

• Length n is 5.
• shift is 7 % 5, which is 2.
• steps is 5 - 2 - 1, which is 2. The walk moves from the head past two nodes, to the node with value 3.
• The new head is the node after 3, which is 4.
• The cut leaves 4 -> 5 -> 1 -> 2 -> 3.

The result is the same as rotating by 2, because 7 is 2 more than one full cycle.

Worked example 3: a list of six with k equal to the length

Take 1 -> 2 -> 3 -> 4 -> 5 -> 6 and k of 6. The length is 6, and 6 % 6 is 0, so shift is 0 and the function returns the head unchanged. Rotating by a full cycle changes nothing, which is the same idea as the modulo step.

Part 2: swap nodes in pairs

What the task asks

Take the list 1 -> 2 -> 3 -> 4 and swap each pair of adjacent nodes. The result is 2 -> 1 -> 4 -> 3. If the list has an odd number of nodes, the last node has no partner and stays where it is. The list 1 -> 2 -> 3 becomes 2 -> 1 -> 3.

The task asks you to relink the nodes, not to copy their values. Swapping the numbers in each pair would give the same printed result for plain integers, but real nodes often carry more data, such as a name and a price. The relinking steps then matter, and they are the steps this lesson practises.

Why use a dummy head

The first pair changes which node is the head. After the swap, node 2 is the head, not node 1. A function that tries to swap from the real head needs a special case for that first pair.

A dummy node removes the special case. It is a placeholder node that sits in front of the real head, and its next field points at the real head. Every pair then has a node before it, which is the placeholder for the first pair and the second node of the previous pair for the rest. At the end the answer is dummy.next, which is the new head whatever it is.

Swapping one pair step by step

Start with dummy -> 1 -> 2 -> 3 -> 4. The pointer prev points at the dummy. The pointers first and second point at the two nodes of the current pair, 1 and 2. Four pointer changes are needed, and their order matters.

1. first->next = second->next; Node 1 now points at node 3. The link to node 2 is gone from node 1, but node 2 still points at 3, so nothing is lost yet.
2. second->next = first; Node 2 now points at node 1.
3. prev->next = second; The dummy now points at node 2.
4. prev = first; Move prev to node 1, which is now the node before the next pair.

After one pass the list reads dummy -> 2 -> 1 -> 3 -> 4. The next pass works on the pair 3 and 4, and the same four steps apply.

The first step must read second->next before the second step changes it. If the second step ran first, second->next would point at first, and the list would no longer contain node 3. The mistakes section shows what happens.

The iterative code

The loop runs while there is a pair to swap. Both prev->next and prev->next->next must be non-null, which means there are at least two nodes left.

Node* swap_pairs_iterative(Node* head) {
    Node dummy(0);
    dummy.next = head;
    Node* prev = &dummy;
    while (prev->next != nullptr && prev->next->next != nullptr) {
        Node* first = prev->next;
        Node* second = first->next;
        first->next = second->next;
        second->next = first;
        prev->next = second;
        prev = first;
    }
    return dummy.next;
}

With an odd count, the last node fails the prev->next->next check, so the loop stops and the last node stays where it is.

The recursive code

Recursion means a function calls itself on a smaller version of the same problem. For this task the smaller problem is "swap the pairs in the rest of the list". The function does three things: it returns the head when there is nothing to swap, it asks the rest of the list to swap its pairs, and it joins the swapped rest to the current pair.

Node* swap_pairs_recursive(Node* head) {
    if (head == nullptr || head->next == nullptr) return head;
    Node* second = head->next;
    head->next = swap_pairs_recursive(second->next);
    second->next = head;
    return second;
}

Trace 1 -> 2 -> 3 -> 4 through the calls:

• The call with head 1 sets second to node 2. It then asks the rest, starting at 3, to swap its pairs.
• The call with head 3 sets second to node 4. It asks the rest after 4, which is empty, so it gets nullptr back. It sets node 3's next to nullptr, sets node 4's next to node 3, and returns node 4. The list from 4 now reads 4 -> 3.
• Back in the call with head 1, head->next is set to node 4, so node 1 now points at the swapped rest. Node 2's next is set to node 1, and node 2 is returned.

The result is 2 -> 1 -> 4 -> 3. Each call waits for the call after it, so the pointer joins happen on the way back up.

The cost is stack space, the memory each unfinished call holds. Every call waits for the next one, so a list of 100,000 nodes makes about 50,000 waiting calls. The recursion lesson later in this module covers that limit.

The full program

The program below has the helpers, both rotate and swap functions, and a main function that runs the examples from this lesson. The show_rotate and show_swap functions print each input and result, and they free the lists they build.

Expected output:

rotate right by 2: 1 -> 2 -> 3 -> 4 -> 5 ==> 4 -> 5 -> 1 -> 2 -> 3
rotate right by 7: 1 -> 2 -> 3 -> 4 -> 5 ==> 4 -> 5 -> 1 -> 2 -> 3
rotate right by 5: 1 -> 2 -> 3 -> 4 -> 5 ==> 1 -> 2 -> 3 -> 4 -> 5
rotate right by 0: 1 -> 2 ==> 1 -> 2
rotate right by 3: (empty) ==> (empty)
iterative: 1 -> 2 -> 3 -> 4 ==> 2 -> 1 -> 4 -> 3
recursive: 1 -> 2 -> 3 -> 4 ==> 2 -> 1 -> 4 -> 3
iterative: 1 -> 2 -> 3 ==> 2 -> 1 -> 3
recursive: 1 -> 2 -> 3 ==> 2 -> 1 -> 3
iterative: 1 ==> 1
recursive: 1 ==> 1

The last four lines of the output show an odd-length list and a single node. A list with one node has no pair, so both versions return it unchanged.

Common mistakes

Forgetting the modulo step

If the code uses k directly instead of k % n, a large k makes steps negative. The walk loop then does nothing, and the cut is made at the wrong place. The modified program was built and run with shift = k; in place of shift = k % n;. Its output for the same inputs is:

rotate right by 7: 1 -> 2 -> 3 -> 4 -> 5 ==> 2 -> 3 -> 4 -> 5 -> 1
rotate right by 5: 1 -> 2 -> 3 -> 4 -> 5 ==> 2 -> 3 -> 4 -> 5 -> 1

Rotating by 7 should give 4 -> 5 -> 1 -> 2 -> 3, and rotating by 5 should change nothing. The program runs without an error and prints a wrong list, which is why the modulo step is worth remembering.

Forgetting to cut the ring

If the final new_tail->next = nullptr; is removed, the list still ends at the old tail, and that tail points back to the head. Printing it would never reach nullptr, so the loop in to_text never stops. The rotated list then has a cycle. This is a common bug in linked list code, and the debugging lab in this module shows how to find one.

Changing the pointers in the wrong order

Here is a tempting ordering of the four pair steps:

second->next = first;
first->next = second->next;
prev->next = second;
prev = first;

The second line now reads second->next, which the first line has just set to first. So first->next is set to first itself, and node 1 points at itself. The loop in the function never reaches the end. The program did not finish when I ran this version with a 10 second limit. It stopped with exit code 124, which is the code timeout uses when it stops a program that is still running. The fix is the original order, where first->next = second->next; comes before second->next = first;.

Losing the head

If the code returns head instead of dummy.next from the iterative function, the answer is wrong after the first swap. Node 1 is still the head pointer, but after the swap node 2 is the first node. Always return the node the dummy points to.

Practice

Exercise 1: Rotate by one

Rotate 10 -> 20 -> 30 -> 40 right by 1. Write the result.

Show the answer

The last node, 40, moves to the front. The result is 40 -> 10 -> 20 -> 30.

Exercise 2: Rotate by a multiple of the length

Rotate 1 -> 2 -> 3 -> 4 -> 5 -> 6 right by 6. Then rotate the same list right by 8. Write both results.

Show the answer

Rotating by 6 is a full cycle, so the list is unchanged: 1 -> 2 -> 3 -> 4 -> 5 -> 6. Rotating by 8 uses 8 % 6, which is 2. The last two nodes move to the front, giving 5 -> 6 -> 1 -> 2 -> 3 -> 4.

Exercise 3: Swap pairs in an odd-length list

Swap the pairs in 1 -> 2 -> 3 -> 4 -> 5. Write the result.

Show the answer

Pairs (1, 2) and (3, 4) swap. The node 5 has no partner and stays last, giving 2 -> 1 -> 4 -> 3 -> 5. The program's iterative version gives the same result for this input.

Exercise 4: Why the dummy head matters

Explain what would go wrong in the iterative function if the code started with Node* prev = head; and had no dummy node.

Show the answer

Without the dummy, the first swap changes the head, so the function needs an extra step that sets the head to node 2 before the loop starts. The first pair would then be handled differently from the rest. A dummy node in front makes every pair look the same, so one loop handles all of them.

Exercise 5: Rotate left

A rotation to the left moves the first nodes to the back. Use rotate_right and the length to write rotate_left(Node* head, int k). Then say what rotate_left of 1 -> 2 -> 3 -> 4 -> 5 by 2 returns.

Show the answer

int count_nodes(const Node* head) {
    int count = 0;
    for (const Node* p = head; p != nullptr; p = p->next) ++count;
    return count;
}
 
Node* rotate_left(Node* head, int k) {
    if (head == nullptr) return head;
    int n = count_nodes(head);
    return rotate_right(head, n - k % n);
}

Rotating left by k is the same as rotating right by n - k % n, because one step to the left is the same as n - 1 steps to the right. For 1 -> 2 -> 3 -> 4 -> 5 and k of 2, the function rotates right by 3, which gives 3 -> 4 -> 5 -> 1 -> 2.

Summary

• Rotating right by k on a list of n nodes is the same as rotating by k % n, so the modulo step handles large values of k.
• Rotation joins the tail to the head, walks to the new tail at index n - shift - 1, and then cuts the ring.
• A dummy node in front of the head removes the special case for the first pair when swapping.
• Pair swapping needs four pointer changes in a fixed order, and reading second->next before changing it is the key rule.
• The recursive version swaps the rest of the list first and joins the pair on the way back up, which uses one stack frame per pair.