Rotate and swap linked list nodes in Python

Why it matters

Rotation and pair swapping both change the order of a list without changing its values. A music player that moves the last few songs to the front of a playlist is rotating. A program that swaps neighbouring items to fix a small mistake in an order is swapping pairs. These operations show up often in list problems, and they are good practice for the pointer work that later lessons in this module depend on, such as reversing groups of nodes.

Both problems move references, not values. A reference is a name that points at an object in memory. In Python, a variable that holds a node holds a reference to it. Writing node.next = other changes which node the link points at, and it copies nothing. To rotate a list, you cut it at one point and join the two pieces in a new order. To swap a pair, you change four references so that two nodes trade places. Nothing is created or deleted.

The list used here is a singly linked list. That is a chain of nodes where each node has one link to the next node. A node is a small object that holds a value and a next reference. The last node's next is None, which is Python's word for "points at nothing". Python has no null keyword, so None plays that role.

Rotating right by k

To rotate a list right by k means to move the last k nodes to the front, keeping their order. Here is a list with five nodes:

1 -> 2 -> 3 -> 4 -> 5 -> None

Rotating right by 2 moves the last two nodes, 4 and 5, to the front:

4 -> 5 -> 1 -> 2 -> 3 -> None

Think of a row of cards on a table. You take the last two cards and place them on top of the pile in the same order. The pile is the same cards, only the starting point has moved.

There is a second way to look at it. The new list starts at the node that comes right after the third node, which is node 4. The node just before it, which is node 3, becomes the new last node. The rest of the work is cutting the list between node 3 and node 4, and joining the old tail back to the old head. This is the plan the code follows.

Step 1: find the length and the tail

We need the length n of the list. The length tells us how many nodes sit in each part of the cut. We also need a reference to the last node. The code calls it the old tail, because we join it to the old head.

n = 1
tail = head
while tail.next is not None:
    tail = tail.next
    n += 1

The variable n starts at 1, because the head is already one node. Each step moves tail forward and adds 1 to n. When tail.next is None, tail is the last node, and n is the number of nodes. This loop walks the whole list once.

The loop starts from head and not from None, so it assumes the list has at least one node. The code checks for an empty list or a one-node list before this loop, and we come back to that in the Common mistakes section.

The test tail.next is not None uses is, not ==. Use is to compare with None, and == for numbers and text.

Step 2: reduce k with modulo

The value k can be bigger than the length. Rotating a five-node list by 5 leaves it unchanged, because every node goes back to its place. Rotating by 7 is the same as rotating by 2, because 7 steps is 5 steps plus 2 more.

The % operator gives the remainder after division. So k % n is the number of real steps:

k = 7, n = 5  ->  shift = 7 % 5 = 2
k = 5, n = 5  ->  shift = 5 % 5 = 0
k = 2, n = 5  ->  shift = 2 % 5 = 2

When shift is 0, the list does not change, and the function returns head right away. The code uses shift for the rest of the work, not k.

For positive n, Python's % always gives a result from 0 up to n - 1, even when k is negative. For example, -7 % 5 is 3 in Python. This lesson only uses positive k.

The rotation by shift means "move the last shift nodes to the front". So with n = 5 and shift = 2, we need to cut after the node that has n - shift nodes up to and including it. The next step turns that into a position.

Step 3: find the new tail

The new tail is the node just before the new head. The new head is the node that will be first after the rotation. Here is the list again, with positions counted from 0:

position:  0   1   2   3   4
value:     1   2   3   4   5

With n = 5 and shift = 2, the new head is at position 3, which holds the value 4. The new tail is at position 2, which holds the value 3. In general the new tail is at position n - shift - 1, because the new head is at position n - shift.

The code walks from the head to that position:

new_tail = head
for _ in range(n - shift - 1):
    new_tail = new_tail.next

range(n - shift - 1) produces the numbers 0, 1, and so on, up to one less than the given number. The loop body runs that many times. With n = 5 and shift = 2, range(2) gives 0 and 1, so the loop runs 2 times, and new_tail ends on the node with value 3. The name _ marks a value that the loop does not use.

Step 4: cut and join

After the new tail is known, three lines finish the work. The order of these lines matters, so read them in order.

new_head = new_tail.next
new_tail.next = None
tail.next = head
return new_head

The first line saves the new head before anything changes. The node after the new tail is node 4, and we keep a reference to it in new_head. The second line cuts the list, so the new tail points to None. The list is now two separate chains: 1 -> 2 -> 3 and 4 -> 5. The third line joins the old tail, node 5, to the old head, node 1. The result is 4 -> 5 -> 1 -> 2 -> 3, and the function returns new_head.

If the first line came after the second, new_head would be None, because new_tail.next would already be None. The function would then return an empty list. This is a common mistake, and it is easy to avoid by saving the reference first.

Here is the full program. It defines a ListNode class, two helper functions, and the rotation. The last lines print results for several inputs.

The output is this.

rotate [1, 2, 3, 4, 5] by 2 -> [4, 5, 1, 2, 3]
rotate [1, 2, 3, 4, 5] by 7 -> [4, 5, 1, 2, 3]
rotate [1, 2, 3, 4, 5] by 5 -> [1, 2, 3, 4, 5]
rotate [1, 2] by 1 -> [2, 1]
rotate [7] by 3 -> [7]
rotate [] by 3 -> []

The first line is the example from above. The second line shows that 7 and 2 give the same answer. The third line shows that rotating by the full length changes nothing. The fourth line is a two-node list: rotating right by 1 swaps the two nodes. The last two lines are the one-node and empty cases, which return at the first check.

*values in from_values(*values) means the function takes any number of arguments and collects them into a tuple. A tuple is a fixed group of values, written with parentheses. So from_values(1, 2, 3) receives values as (1, 2, 3). The * before values in a call, as in from_values(*values), does the reverse: it spreads a list or tuple into separate arguments.

Example: rotating by a small k in a longer list

Take the list 1 -> 2 -> 3 -> 4 -> 5 -> 6 and rotate by 4. The length is 6, and shift is 4 % 6, which is 4. The new tail is at position 6 - 4 - 1, which is 1, so the new tail is the node with value 2. The new head is node 3. The cut and join give 3 -> 4 -> 5 -> 6 -> 1 -> 2.

Check it with one line. Add this line at the end of the program above:

print(to_list(rotate_right(from_values(1, 2, 3, 4, 5, 6), 4)))

The output is [3, 4, 5, 6, 1, 2], which matches the hand calculation.

Swapping pairs

The second problem takes a list and swaps each pair of neighbouring nodes. The first and second nodes trade places, then the third and fourth, and so on. If the list has an odd number of nodes, the last node has no partner and stays where it is.

input:   1 -> 2 -> 3 -> 4 -> None
output:  2 -> 1 -> 4 -> 3 -> None
 
input:   1 -> 2 -> 3 -> 4 -> 5 -> None
output:  2 -> 1 -> 4 -> 3 -> 5 -> None

The problem is about nodes, not values. Swapping the values inside the nodes gives the same printed list, and the Practice section shows that version. The difference shows up when other code holds a reference to a node.

The dummy head

A swap changes the first node of the list when the first pair is swapped. The old head becomes the second node, and the old second node becomes the new head. A function that returns the head then has to handle this case as a special case.

A dummy head avoids the special case. A dummy head is an extra node placed in front of the real head. Its next field points to the real head. Every pair, including the first, now has a node before it, and that node is always there to link to. When the work is done, the function returns dummy.next, which is the real head after all the swaps.

dummy = ListNode(0, head)

The constructor used here takes a value and a next node. The value 0 is never read. It is only a placeholder.

Swapping pairs iteratively

The iterative version uses a while loop. It keeps a reference called prev that points to the node just before the current pair. In each pass, prev.next is the first node of the pair, and prev.next.next is the second.

def swap_pairs_iterative(head):
    dummy = ListNode(0, head)
    prev = dummy
    while prev.next is not None and prev.next.next is not None:
        first = prev.next
        second = first.next
        first.next = second.next
        second.next = first
        prev.next = second
        prev = first
    return dummy.next

The loop condition checks two things. The first check, prev.next is not None, means there is a node to swap. The second check, prev.next.next is not None, means there is a second node to swap with. If either check fails, the list is done. An odd last node fails the second check, and the loop stops, leaving the last node in its place.

Now the four reference changes, in order. Start with this list, where prev is the dummy and the pair is 1 and 2:

dummy -> 1 -> 2 -> 3 -> 4 -> None

Line one, first = prev.next, makes first point to node 1. Line two, second = first.next, makes second point to node 2. Now both nodes have names, and no reference to them has changed yet.

Line three, first.next = second.next, makes node 1 point to node 3. Node 2 still points to node 3, which is correct for now. The list still has node 2 in it, but node 1 now skips it. This is the step that needs the saved second. If second had not been saved, we would not know where node 2 was.

Line four, second.next = first, makes node 2 point to node 1. Now the chain goes 2 to 1 to 3.

Line five, prev.next = second, makes the dummy point to node 2. The list is now dummy -> 2 -> 1 -> 3 -> 4.

Line six, prev = first, moves prev to node 1. Node 1 is now the node before the next pair, which starts at node 3. The loop runs again on nodes 3 and 4.

The result is dummy -> 2 -> 1 -> 4 -> 3. When the loop ends, dummy.next is node 2, the new head.

Here is the function run on 1 -> 2 -> 3 -> 4 -> 5:

print(to_list(swap_pairs_iterative(from_values(1, 2, 3, 4, 5))))

The output is [2, 1, 4, 3, 5]. The last node stays because its pair check fails.

Swapping pairs recursively

A recursive function is one that calls itself on a smaller problem. The recursive version of pair swapping says: swap the first pair, then swap the pairs in the rest of the list. The rest of the list is the same kind of problem, only shorter, so the same function solves it.

The recursive version needs a dummy head too, and the simplest shape is a helper that takes the node just before the pair. Here is the helper, with the swap steps from the iterative version:

def swap_from(prev):
    first = prev.next
    if first is None or first.next is None:
        return
    second = first.next
    first.next = second.next
    second.next = first
    prev.next = second
    swap_from(first)
 
 
def swap_pairs_recursive(head):
    dummy = ListNode(0, head)
    swap_from(dummy)
    return dummy.next

The helper swap_from does the same four reference changes as the loop. The difference is at the end. After swapping, first is the second node of the new pair, and it is now the node just before the rest of the list. So the helper calls swap_from(first), which handles the next pair with first as the new prev.

The first if is the base case. A base case is the situation where the function stops calling itself. Here there are two reasons to stop: there is no node to swap, or there is only one node left. Both mean the rest of the list has nothing to swap, so the function returns. return with no value gives None.

Trace 1 -> 2 -> 3 -> 4 -> 5 with the recursive version. The first call is swap_from(dummy), which swaps 1 and 2 and then calls swap_from(node 1). That call looks at 3 and 4, swaps them, and calls swap_from(node 3). That call sees node 5 with no partner, returns, and the calls unwind. The output is the same as the iterative version:

iterative [2, 1, 4, 3, 5]
recursive [2, 1, 4, 3, 5]

Each pair takes one level of the call stack. The call stack is the list of calls that are still running. Python keeps it in memory, and each running call takes one frame, a block of memory that holds the function's parameters and local variables.

Python limits how deep the stack can grow. The limit is called the recursion limit. Check it with sys.getrecursionlimit(). In Python 3.14 on the machine used for this lesson, it is 1000. A call that would go past the limit raises RecursionError.

The recursive swap was run on lists of different sizes with that default limit. It worked for 600 pairs, which is 1200 nodes. It raised RecursionError for 1000 pairs. The exact count depends on how deep the program already is when the swap starts, so the safe rule is that a recursive version fails somewhere well below the limit. For a list with 5000 pairs, the run ended with this:

  File "rotate.py", line 180, in swap_from
    swap_from(first)
    ~~~~~~~~~^^^^^^^
  [Previous line repeated 995 more times]
RecursionError: maximum recursion depth exceeded

The file name and line number depend on where the code is saved. The last line is the part to read. For this lesson, the iterative version is the safer choice for long lists, and the recursive version is the clearer one for short lists. The next lesson on recursion and the recursion limit covers the details.

Here is a complete program for pair swapping. It has both versions, a check that the two agree, and the output.

The output is this.

iterative [2, 1, 4, 3, 5]
recursive [2, 1, 4, 3, 5]
same result: True

Common mistakes

Off by one in the new tail

The new tail is at position n - shift - 1, with the - 1. If you leave out the - 1, the cut moves one node forward, and the rotation is wrong. Here is the loop with the wrong range, range(n - shift), run on 1 -> 2 -> 3 -> 4 -> 5 with k = 2:

off by one, rotate [1,2,3,4,5] by 2 -> [5, 1, 2, 3, 4]

The answer is a rotation by one step, not two, because the cut was one node too far.

Leaving out first.next = second.next

In the swap, the line first.next = second.next must run before second.next changes. If that line is left out, first.next keeps pointing at second, and the nodes form a loop. A loop here means a chain of links that goes back to a node already seen, so it never reaches None. Here is a version without that line:

def forget_saved(head):
    dummy = ListNode(0, head)
    prev = dummy
    while prev.next is not None and prev.next.next is not None:
        first = prev.next
        second = first.next
        second.next = first
        prev.next = second
        prev = first
    return dummy.next

Python prints nothing for this function, because the loop never ends. Running it under the timeout command with a limit of 5 seconds ends with exit code 124, which is the code that timeout returns when it had to stop the program. Node 1 and node 2 point at each other, and later node 1 points at itself, so the loop goes around forever.

The fix is the line first.next = second.next before second.next = first. Its position in the code is the reason for the order.

Forgetting the k modulo

If the code uses k directly and skips k % n, a k larger than the length goes wrong. With n = 5 and k = 7, the loop for _ in range(n - k - 1) runs zero times, because range with a negative number gives no values. The new tail stays at the head, and the result is the list rotated by one step: 2 -> 3 -> 4 -> 5 -> 1. Using k % n fixes this.

[2, 3, 4, 5, 1]

Missing check on the empty list

The first line of rotate_right checks head is None and head.next is None. Without that check, the function reads tail.next on an empty list, where tail is None. Python then raises an AttributeError, because None has no attribute called next. Running the version without the check on an empty list gave this last part of the error:

    while tail.next is not None:
          ^^^^^^^^^
AttributeError: 'NoneType' object has no attribute 'next'

The swap function does not need the same check, because its loop condition checks prev.next first, and dummy.next is None on an empty list. The loop then stops at once.

Practice

Exercise 1

Rotate the list 1 -> 2 -> 3 right by 1. Write the result as a list of values.

Show the answer

The length is 3 and the shift is 1 % 3, which is 1. The new tail is at position 3 - 1 - 1, which is 1, so the new tail is node 2. The new head is node 3. The result is 3 -> 1 -> 2, which is [3, 1, 2].

Exercise 2

Rotate 1 -> 2 -> 3 -> 4 -> 5 -> 6 right by 4 with the code. Check the answer by hand before you run it.

Show the answer

The shift is 4, and the new tail is at position 1, which is node 2. The new head is node 3. The result is [3, 4, 5, 6, 1, 2]. The code prints the same list.

Exercise 3

Swap the pairs of 1 -> 2 -> 3 with the iterative version. Say what happens to the last node.

Show the answer

The first pair, 1 and 2, swaps to give 2 and 1. The third node has no partner, so the loop condition prev.next.next is not None is false when prev is node 1. The loop stops and node 3 stays last. The result is [2, 1, 3].

Exercise 4

Rotating by k = 0 returns the same list. Explain why the code does not need to walk the list to find the new tail when k = 0, and say which line handles this case.

Show the answer

When k = 0, shift is 0 % n, which is 0. The line if shift == 0: return head returns the head before the loop that finds the new tail. The code still walks the list to find n first, because n is needed to compute shift. The early return saves only the second walk.

Exercise 5

Write a version of pair swapping that swaps the values inside the nodes, not the nodes themselves, and check that it gives the same values for 1 -> 2 -> 3 -> 4 -> 5. Then say why this version can break a program that holds a reference to node 3.

Show the answer

def swap_values(head):
    cur = head
    while cur is not None and cur.next is not None:
        cur.val, cur.next.val = cur.next.val, cur.val
        cur = cur.next.next
    return head

The line cur.val, cur.next.val = cur.next.val, cur.val swaps two values in one step. Python evaluates the right side first, so both old values are read before either is written.

The output for 1 -> 2 -> 3 -> 4 -> 5 is [2, 1, 4, 3, 5], the same values as the node version. The difference is in which node holds which value. Suppose another part of the program keeps a reference to the node that held 3. After the value swap, that node holds 4, so the reference now reads the wrong value. After the node swap, that node still holds 3 and has moved to the fourth position.

Summary

• A right rotation by k cuts the list after the node at position n - shift - 1 and joins the old tail to the old head, where shift is k % n.
• Save the new head before you cut the list, or the cut will lose it.
• A dummy head lets pair swapping treat the first pair the same as every other pair.
• Each pair swap changes four references in a fixed order, and the second node's next must be saved before it is overwritten.
• The recursive pair swap calls itself once per pair, so it uses one frame per pair, and Python's recursion limit caps how many pairs it can handle.