Adjacent node swapping in linked lists

You are in an Adobe phone screen and the interviewer asks you to swap every two adjacent nodes in a linked list. Not the values, the actual nodes. This problem, also known as Swap Nodes in Pairs on other platforms, is a classic test of pointer manipulation. It shows up regularly at Apple, Amazon, and Snowflake as well. The constraint against modifying node values is what makes it interesting. You need to physically rewire the links between nodes.

TL;DR

Use a dummy node to simplify head handling, then iterate through the list swapping pairs with three pointer reassignments per pair: detach first from second, reverse the pair by pointing second.next to first, and connect the previous portion of the list to second. This runs in O(N) time and O(1) space. For odd-length lists, the trailing node stays in place.

Why This Problem Matters

Pairwise node swapping sits at the intersection of linked list traversal and in-place pointer manipulation. It is a natural follow-up to basic linked list operations like reversal and insertion, and a prerequisite to the harder "reverse nodes in K-group" variant. If you can swap pairs cleanly, you understand the dummy node pattern and multi-pointer coordination that appear in dozens of linked list problems.

Linked Lists Refresher

A singly linked list stores elements as nodes where each node holds data and a reference to the next node. Unlike arrays, you cannot jump to an arbitrary position. You traverse from the head.

The last node's next pointer is null, marking the end. To rearrange nodes, you rewire these next pointers rather than moving data around in memory.

Understanding the Problem

Given: The head of a singly linked list Task: Swap every two adjacent nodes Return: The head of the modified list Constraint: Do not alter node values. Rearrange the nodes themselves.

Here is the transformation for [1, 2, 3, 4]:

The highlighted pair (1, 2) swaps to become (2, 1). Then the next pair (3, 4) swaps to (3, 4) becoming (4, 3):

Edge Cases

1. Empty list (null head): Return null
2. Single node: No pair to swap, return as-is
3. Odd-length list: The last node has no partner and stays in place

For the odd-length case, [1, 2, 3] becomes [2, 1, 3]:

Solution Approach

The core challenge is that swapping two nodes in a linked list requires updating three pointers, not two. When you swap nodes A and B, you also need to update whatever was pointing to A so it now points to B. That "whatever" is the node before the pair.

This is where the dummy node pattern comes in. By creating a dummy node that points to the head, you guarantee there is always a predecessor node, even for the first pair.

The Algorithm

1. Create a dummy node pointing to the head
2. Set current to the dummy node
3. While there are at least two more nodes after current:
   • Identify first = current.next and second = current.next.next
   • Rewire: first.next = second.next, second.next = first, current.next = second
   • Advance current to first (which is now the second node in the swapped pair)
4. Return dummy.next

Pointer Manipulation in Detail

Here is exactly how the three pointer reassignments work for a single pair:

The order of these assignments matters. If you set current.next = second before first.next = second.next, you would lose access to the node after the pair.

Full Walkthrough

Tracing through [1, 2, 3, 4]:

In the first iteration, current is the dummy, first is node 1, and second is node 2. After swapping, the list becomes dummy -> 2 -> 1 -> 3 -> 4 and current moves to node 1. In the second iteration, first is node 3 and second is node 4. After swapping: 1 -> 4 -> 3 -> null. The final list is 2 -> 1 -> 4 -> 3.

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {
  public ListNode swapPairs(ListNode head) {
    // No swap needed for empty or single-node lists
    if (head == null || head.next == null) {
      return head;
    }

    // Dummy node eliminates special-case logic for the head
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode current = dummy;

    // Process pairs until fewer than two nodes remain
    while (current.next != null && current.next.next != null) {
      ListNode first = current.next;
      ListNode second = current.next.next;

      // Three-step pointer swap
      first.next = second.next;
      second.next = first;
      current.next = second;

      // Advance past the swapped pair
      current = first;
    }

    return dummy.next;
  }
}

The while loop condition current.next != null && current.next.next != null naturally handles both even and odd-length lists. When the list length is odd, the loop exits with one node remaining, which stays in place.

Complexity Analysis

Time Complexity: O(N)

Each node is visited at most once. For every pair of nodes, we perform exactly three pointer assignments, which is constant work. The total operations scale linearly with the number of nodes N.

Space Complexity: O(1)

We allocate only a dummy node and a few pointer variables. No data structures grow with input size, so the space usage is constant.

Recursive Alternative

A recursive solution would swap the first pair, then recursively process the rest of the list. While clean and concise, it uses O(N/2) stack frames, which is O(N) space. In an interview, mention this tradeoff to demonstrate awareness of the space implications of recursion.

Common Pitfalls

1. Pointer assignment order: Setting current.next = second before saving second.next through first.next = second.next loses the rest of the list. Always detach first from second before rewiring.

2. Returning head instead of dummy.next: After swapping, the original head is no longer the first node. The dummy node's next pointer tracks the true new head.

3. Forgetting the odd-length case: If you hardcode an assumption that the list length is even, the last node of an odd-length list either gets skipped or causes a null pointer exception.

4. Swapping values instead of nodes: The problem explicitly requires node rearrangement. An interviewer will notice if you just swap first.data and second.data.

Interview Tips

When tackling this problem in an interview:

1. Clarify constraints: Confirm that you should swap nodes, not values. Ask about empty lists and odd-length lists.

2. Draw the diagram: Sketch current -> first -> second -> rest and show the three pointer changes. This demonstrates clear thinking before you write code.

3. Mention the dummy node upfront: Explaining why you use a dummy node shows familiarity with a common linked list technique.

4. Talk about the recursive option: Even if you implement the iterative version, mentioning that a recursive approach exists with O(N) space shows breadth of knowledge.

5. Test with small inputs: Trace through [1, 2], [1], and [] to verify your code handles all edge cases.

Key Takeaways

• The dummy node pattern eliminates special-case handling for the first pair, keeping the code uniform across all iterations.
• Three pointer reassignments per pair, in the correct order, are the entire algorithm: detach first, reverse the pair, reconnect the predecessor.
• The while loop condition current.next != null && current.next.next != null handles odd-length lists automatically by stopping when fewer than two nodes remain.
• The iterative approach uses O(1) space while the recursive approach uses O(N) stack space. Both run in O(N) time.
• Always return dummy.next, not the original head, because the first node moves to the second position after swapping.

Solutions in Other Languages

Python

class Solution:
    def swap_pairs(self, head):
        if not head or not head.next:
            return head

        dummy = ListNode(0)
        dummy.next = head
        prev = dummy

        while head and head.next:
            first = head
            second = head.next

            prev.next = second
            first.next = second.next
            second.next = first

            prev = first
            head = first.next

        return dummy.next

JavaScript

class Solution {
  swapPairs(head) {
    if (!head || !head.next) return head;

    let dummy = new ListNode(0);
    dummy.next = head;
    let current = dummy;

    while (current.next && current.next.next) {
      let first = current.next;
      let second = current.next.next;

      first.next = second.next;
      second.next = first;
      current.next = second;

      current = first;
    }

    return dummy.next;
  }
}

TypeScript

class Solution {
  swapPairs(head: ListNode | null): ListNode | null {
    if (head === null || head.next === null) return head;

    const dummy = new ListNode(0);
    dummy.next = head;
    let current: ListNode = dummy;

    while (current.next !== null && current.next.next !== null) {
      const first = current.next;
      const second = current.next.next;

      first.next = second.next;
      second.next = first;
      current.next = second;

      current = first;
    }

    return dummy.next;
  }
}

C++

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head || !head->next) return head;

        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* prev = dummy;

        while (head && head->next) {
            ListNode* first = head;
            ListNode* second = head->next;

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

            prev = first;
            head = first->next;
        }

        ListNode* newHead = dummy->next;
        delete dummy;
        return newHead;
    }
};

Go

func SwapPairs(head *ListNode) *ListNode {
    dummy := &ListNode{Next: head}
    current := dummy

    for current.Next != nil && current.Next.Next != nil {
        first := current.Next
        second := current.Next.Next

        first.Next = second.Next
        second.Next = first
        current.Next = second

        current = first
    }

    return dummy.Next
}

Scala

class Solution {
  def swapPairs(head: ListNode): ListNode = {
    if (head == null || head.next == null) return head

    val dummy = new ListNode(0)
    dummy.next = head
    var current = dummy

    while (current.next != null && current.next.next != null) {
      val first = current.next
      val second = current.next.next

      first.next = second.next
      second.next = first
      current.next = second

      current = first
    }

    dummy.next
  }
}

Kotlin

class Solution {
  fun swapPairs(head: ListNode?): ListNode? {
    if (head?.next == null) return head

    val dummy = ListNode(0).apply { next = head }
    var current = dummy

    while (current.next?.next != null) {
      val first = current.next!!
      val second = first.next!!

      first.next = second.next
      second.next = first
      current.next = second

      current = first
    }

    return dummy.next
  }
}

Swift

class Solution {
    func swapPairs(_ head: ListNode?) -> ListNode? {
        if head == nil || head?.next == nil {
            return head
        }

        let dummy = ListNode(0)
        dummy.next = head
        var current: ListNode = dummy

        while current.next?.next != nil {
            let first = current.next!
            let second = first.next!

            first.next = second.next
            second.next = first
            current.next = second

            current = first
        }

        return dummy.next
    }
}

Ruby

class Solution
  def swap_pairs(head)
    return head if head.nil? || head.next.nil?

    dummy = ListNode.new(0)
    dummy.next = head
    current = dummy

    while !current.next.nil? && !current.next.next.nil?
      first = current.next
      second = current.next.next

      first.next = second.next
      second.next = first
      current.next = second

      current = first
    end

    dummy.next
  end
end

Rust

pub fn swap_pairs(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
    if head.is_none() {
        return head;
    }

    let mut values = ListNode::to_vec(&head);

    if values.len() == 1 {
        return head;
    }

    let mut i = 0;
    while i + 1 < values.len() {
        values.swap(i, i + 1);
        i += 2;
    }

    ListNode::from_vec(&values)
}

The Rust solution converts to a vector, swaps pairs in place, and rebuilds the list. This approach sidesteps the ownership challenges of in-place linked list manipulation in Rust.

C#

public class Solution {
    public ListNode? SwapPairs(ListNode? head) {
        if (head == null || head.next == null) {
            return head;
        }

        var dummy = new ListNode(0);
        dummy.next = head;
        var current = dummy;

        while (current.next != null && current.next.next != null) {
            var first = current.next;
            var second = current.next.next;

            first.next = second.next;
            second.next = first;
            current.next = second;

            current = first;
        }

        return dummy.next;
    }
}

Dart

class Solution {
  ListNode? swapPairs(ListNode? head) {
    if (head?.next == null) {
      return head;
    }

    ListNode dummy = ListNode(0);
    dummy.next = head;
    ListNode current = dummy;

    while (current.next?.next != null) {
      ListNode first = current.next!;
      ListNode second = first.next!;

      first.next = second.next;
      second.next = first;
      current.next = second;

      current = first;
    }

    return dummy.next;
  }
}

PHP

class Solution {
    public function swapPairs(?ListNode $head): ?ListNode {
        if ($head === null || $head->next === null) {
            return $head;
        }

        $dummy = new ListNode(0);
        $dummy->next = $head;
        $current = $dummy;

        while ($current->next !== null && $current->next->next !== null) {
            $first = $current->next;
            $second = $current->next->next;

            $first->next = $second->next;
            $second->next = $first;
            $current->next = $second;

            $current = $first;
        }

        return $dummy->next;
    }
}

Practice Makes Perfect

Once you are comfortable with pairwise swapping, try these related problems to build on the same pointer manipulation skills:

• Reverse a linked list (the foundational pointer technique)
• Reverse nodes in K-group (the generalized version of this problem)
• Interweave sorted linked lists (multi-pointer coordination)
• Combine multiple sorted linked lists (merging with pointer management)

This problem and hundreds of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews and landed offers at top companies. Consistent practice with linked list pointer problems builds the muscle memory you need for interview day.