Rotate and Swap Operations on Linked Lists

Rotation and swap operations rearrange linked list nodes without changing their values. These problems test your ability to manipulate pointers precisely — one wrong assignment creates a cycle or loses nodes. Let us break down the three most common variants.

The ListNode Class

class ListNode:
    """Standard singly linked list node."""
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def __repr__(self):
        parts, node, seen = [], self, set()
        while node and id(node) not in seen:
            seen.add(id(node))
            parts.append(str(node.val))
            node = node.next
        return " → ".join(parts)


def build_list(values):
    """Build a linked list from a Python list."""
    if not values:
        return None
    head = ListNode(values[0])
    current = head
    for val in values[1:]:
        current.next = ListNode(val)
        current = current.next
    return head

Problem 1: Rotate List by K Positions (LeetCode 61)

Problem: Given a linked list and integer k, rotate the list to the right by k places.

Example:

Input:  1 → 2 → 3 → 4 → 5, k = 2
Output: 4 → 5 → 1 → 2 → 3

The last 2 nodes (4 → 5) move to the front.

The Key Insight

Rotating right by k is equivalent to:

1. Making the list circular (connect tail to head)
2. Finding the new tail at position n - k from the start
3. Breaking the circle at that point

If k >= n, we only need to rotate by k % n (since rotating by n gives the original list).

Solution

def rotate_right(head, k):
    """
    Rotate linked list to the right by k places.
    
    LeetCode 61 — Rotate List
    Time: O(n), Space: O(1)
    """
    if not head or not head.next or k == 0:
        return head

    # Step 1: Find length and tail
    length = 1
    tail = head
    while tail.next:
        tail = tail.next
        length += 1

    # Step 2: Normalize k
    k = k % length
    if k == 0:
        return head  # No rotation needed

    # Step 3: Make circular
    tail.next = head

    # Step 4: Find new tail (n - k steps from head)
    steps_to_new_tail = length - k
    new_tail = head
    for _ in range(steps_to_new_tail - 1):
        new_tail = new_tail.next

    # Step 5: Break the circle
    new_head = new_tail.next
    new_tail.next = None

    return new_head


# Test
head = build_list([1, 2, 3, 4, 5])
print("Before:", head)                # 1 → 2 → 3 → 4 → 5
print("k=2:  ", rotate_right(head, 2))  # 4 → 5 → 1 → 2 → 3

head = build_list([0, 1, 2])
print("Before:", head)                # 0 → 1 → 2
print("k=4:  ", rotate_right(head, 4))  # 2 → 0 → 1

Trace Through

List: 1 → 2 → 3 → 4 → 5, k = 2

Step 1: length = 5, tail = node(5)
Step 2: k = 2 % 5 = 2
Step 3: Make circular: 5.next = 1
Step 4: steps_to_new_tail = 5 - 2 = 3
        Walk 2 steps from head: 1 → 2 → 3
        new_tail = node(3)
Step 5: new_head = node(4), 3.next = None

Result: 4 → 5 → 1 → 2 → 3

Rotate Left

To rotate left by k, rotate right by n - k:

def rotate_left(head, k):
    """
    Rotate linked list to the left by k places.
    Time: O(n), Space: O(1)
    """
    if not head or not head.next or k == 0:
        return head

    # Find length
    length = 0
    current = head
    while current:
        length += 1
        current = current.next

    # Rotate left by k = rotate right by (n - k)
    effective_k = length - (k % length)
    return rotate_right(head, effective_k)


# Test
head = build_list([1, 2, 3, 4, 5])
print("Left k=2:", rotate_left(head, 2))  # 3 → 4 → 5 → 1 → 2

Problem 2: Swap Nodes in Pairs (LeetCode 24)

Problem: Given a linked list, swap every two adjacent nodes. You must swap the actual nodes, not just their values.

Example:

Input:  1 → 2 → 3 → 4
Output: 2 → 1 → 4 → 3

Iterative Solution

The trick is to use a dummy node before the head and process two nodes at a time:

def swap_pairs(head):
    """
    Swap every two adjacent nodes.
    
    LeetCode 24 — Swap Nodes in Pairs
    Time: O(n), Space: O(1)
    """
    dummy = ListNode(0, head)
    prev = dummy

    while prev.next and prev.next.next:
        # Identify the pair
        first = prev.next
        second = prev.next.next

        # Swap the pair
        first.next = second.next   # first skips second
        second.next = first        # second points to first
        prev.next = second         # previous points to second

        # Move to next pair
        prev = first  # first is now the second node in the swapped pair

    return dummy.next


# Test
head = build_list([1, 2, 3, 4])
print("Before:", head)              # 1 → 2 → 3 → 4
print("After: ", swap_pairs(head))  # 2 → 1 → 4 → 3

head = build_list([1, 2, 3, 4, 5])
print("Before:", head)              # 1 → 2 → 3 → 4 → 5
print("After: ", swap_pairs(head))  # 2 → 1 → 4 → 3 → 5

Trace Through

List: 1 → 2 → 3 → 4
dummy → 1 → 2 → 3 → 4
prev = dummy

Iteration 1:
  first = 1, second = 2
  1.next = 3       (skip 2)
  2.next = 1       (2 points to 1)
  dummy.next = 2   (prev points to 2)
  prev = 1         (advance)
  State: dummy → 2 → 1 → 3 → 4

Iteration 2:
  first = 3, second = 4
  3.next = None    (skip 4)
  4.next = 3       (4 points to 3)
  1.next = 4       (prev points to 4)
  prev = 3         (advance)
  State: dummy → 2 → 1 → 4 → 3

prev.next (3.next = None) — loop ends.
Result: 2 → 1 → 4 → 3

Recursive Solution

Recursion makes the logic more elegant but uses O(n/2) = O(n) stack space:

def swap_pairs_recursive(head):
    """
    Swap nodes in pairs using recursion.
    Time: O(n), Space: O(n) — call stack
    """
    # Base cases: 0 or 1 nodes
    if not head or not head.next:
        return head

    first = head
    second = head.next

    # Recursively swap the rest of the list
    first.next = swap_pairs_recursive(second.next)
    second.next = first

    return second  # second is now the head of this pair


# Test
head = build_list([1, 2, 3, 4, 5])
print("Recursive:", swap_pairs_recursive(head))  # 2 → 1 → 4 → 3 → 5

Problem 3: Swap Kth Node From Start and End

Problem: Given a linked list and integer k, swap the values of the kth node from the beginning and the kth node from the end (1-indexed).

Example:

Input:  1 → 2 → 3 → 4 → 5, k = 2
Output: 1 → 4 → 3 → 2 → 5

The 2nd node from start (value 2) swaps with the 2nd node from end (value 4).

Solution with Value Swap

The simplest approach swaps values, which is acceptable for this problem:

def swap_kth_values(head, k):
    """
    Swap values of kth node from start and kth from end.
    
    LeetCode 1721 — Swapping Nodes in a Linked List
    Time: O(n), Space: O(1)
    """
    # Find kth node from start
    front = head
    for _ in range(k - 1):
        front = front.next

    # Use two-pointer technique to find kth from end
    # Start back pointer at head, advance front pointer to end
    back = head
    temp = front
    while temp.next:
        temp = temp.next
        back = back.next

    # Swap values
    front.val, back.val = back.val, front.val

    return head


# Test
head = build_list([1, 2, 3, 4, 5])
print("Before:", head)                     # 1 → 2 → 3 → 4 → 5
print("k=2:  ", swap_kth_values(head, 2))  # 1 → 4 → 3 → 2 → 5

head = build_list([7, 9, 6, 6, 7, 8, 3, 0, 9, 5])
print("k=5:  ", swap_kth_values(head, 5))  # 7 → 9 → 6 → 6 → 8 → 7 → 3 → 0 → 9 → 5

Finding Kth From End: The Two-Pointer Trick

The key technique is:

1. Advance the first pointer k steps from head
2. Start the second pointer at head
3. Move both forward until the first pointer reaches the end
4. The second pointer is now at the kth node from the end

This works because the gap between the two pointers is exactly k, so when the first hits the end, the second is k from the end.

Solution with Node Swap (No Value Change)

If the interviewer insists on swapping nodes rather than values, you need to track the predecessors:

def swap_kth_nodes(head, k):
    """
    Swap actual nodes (not values) of kth from start and kth from end.
    Time: O(n), Space: O(1)
    """
    dummy = ListNode(0, head)

    # Find kth from start and its predecessor
    front_prev = dummy
    for _ in range(k - 1):
        front_prev = front_prev.next
    front = front_prev.next

    # Find kth from end and its predecessor
    back_prev = dummy
    temp = front
    while temp.next:
        temp = temp.next
        back_prev = back_prev.next
    back = back_prev.next

    # If same node, nothing to do
    if front is back:
        return dummy.next

    # Swap the nodes
    front_prev.next = back
    back_prev.next = front
    front.next, back.next = back.next, front.next

    return dummy.next


# Test
head = build_list([1, 2, 3, 4, 5])
print("Node swap k=2:", swap_kth_nodes(head, 2))  # 1 → 4 → 3 → 2 → 5

Edge Case: Adjacent Nodes

When the two kth nodes are adjacent, the basic swap logic still works because we track predecessors separately. However, there is a subtle case: if front_prev is back or back_prev is front (one is the predecessor of the other), we need to be careful:

def swap_kth_nodes_safe(head, k):
    """
    Swap kth nodes, handling adjacent and same-node cases.
    Time: O(n), Space: O(1)
    """
    dummy = ListNode(0, head)

    # Find length
    length = 0
    current = head
    while current:
        length += 1
        current = current.next

    # If kth from start == kth from end, nothing to do
    if k == length - k + 1:
        return head

    # Find kth from start with predecessor
    front_prev = dummy
    for _ in range(k - 1):
        front_prev = front_prev.next
    front = front_prev.next

    # Find (length - k + 1)th from start with predecessor
    back_prev = dummy
    for _ in range(length - k):
        back_prev = back_prev.next
    back = back_prev.next

    # Swap
    front_prev.next = back
    back_prev.next = front
    front.next, back.next = back.next, front.next

    return dummy.next

Reverse Nodes in K-Group (LeetCode 25)

A harder variant: instead of swapping pairs, reverse every group of k nodes:

def reverse_k_group(head, k):
    """
    Reverse nodes in groups of k. If remaining nodes < k, leave as-is.
    
    LeetCode 25 — Reverse Nodes in k-Group
    Time: O(n), Space: O(1)
    """
    # Check if there are at least k nodes remaining
    count = 0
    current = head
    while current and count < k:
        current = current.next
        count += 1
    if count < k:
        return head  # Not enough nodes to reverse

    # Reverse k nodes
    prev = None
    current = head
    for _ in range(k):
        next_node = current.next
        current.next = prev
        prev = current
        current = next_node

    # head is now the tail of the reversed group
    # Recursively process the rest and connect
    head.next = reverse_k_group(current, k)

    return prev  # prev is the new head of this group


# Test
head = build_list([1, 2, 3, 4, 5])
print("k=2:", reverse_k_group(head, 2))  # 2 → 1 → 4 → 3 → 5

head = build_list([1, 2, 3, 4, 5])
print("k=3:", reverse_k_group(head, 3))  # 3 → 2 → 1 → 4 → 5

Complexity Summary

Operation	Time	Space	Key Technique
Rotate right by k	O(n)	O(1)	Circular list + break
Swap pairs (iterative)	O(n)	O(1)	Dummy node + prev pointer
Swap pairs (recursive)	O(n)	O(n)	Recursion stack
Swap kth nodes (values)	O(n)	O(1)	Two-pointer gap
Swap kth nodes (nodes)	O(n)	O(1)	Predecessor tracking
Reverse k-group	O(n)	O(n/k)	Recursive reversal

Common Mistakes

1. Not normalizing k in rotation. If k = 7 and n = 5, you should rotate by 7 % 5 = 2. Forgetting this causes out-of-bounds traversal.

2. Losing the connection in pair swapping. The prev pointer must point to the new first node of each swapped pair. If you forget to update prev.next, you lose part of the list.

3. Off-by-one in kth-from-end. Remember that k is 1-indexed. The kth node from the start requires k - 1 steps from head, not k steps.

4. Not handling k = 1 or k = n. When k = 1, the kth from start is the head, and the kth from end is the tail. When k = n, it is the opposite. Your logic must handle both.

5. Adjacent node swap corruption. When the two nodes being swapped are adjacent, swapping next pointers can create self-loops if not done carefully. Always use the predecessor-based approach.

Practice Problems

1. LeetCode 61 — Rotate List: Right rotation by k (Medium)
2. LeetCode 24 — Swap Nodes in Pairs: Pairwise swap (Medium)
3. LeetCode 25 — Reverse Nodes in k-Group: Generalized group reversal (Hard)
4. LeetCode 1721 — Swapping Nodes in a Linked List: Swap kth from both ends (Medium)
5. LeetCode 92 — Reverse Linked List II: Reverse between positions left and right (Medium)
6. LeetCode 189 — Rotate Array: Array version of rotation for comparison (Medium)

Key Takeaways

• Rotation is elegantly solved by making the list circular and breaking at the right point. Always normalize k with modulo.
• Pair swapping requires a dummy node and careful prev tracking. The iterative version is O(1) space.
• Kth-from-end uses the two-pointer gap technique: advance one pointer k steps, then move both until the first hits the end.
• Node swapping (as opposed to value swapping) requires tracking predecessors and is significantly more complex.
• Always draw out pointer changes on paper before coding — one wrong assignment corrupts the entire list.