Reverse a linked list in pairs

You're whiteboarding at a Microsoft on-site when the interviewer draws a linked list on the board and says, "Swap every two adjacent nodes and return the modified list. Don't just swap the values, actually move the nodes." This is the classic Swap Nodes in Pairs problem, and it shows up frequently at companies like Microsoft and Amazon. It builds directly on basic linked list reversal, but the pairwise constraint introduces a subtle twist in how you manage pointers.

TL;DR

Use a dummy node pointing to the head, and a prev pointer starting at the dummy. In each iteration, identify the pair (first and second), then perform three pointer reassignments: prev.next = second, first.next = second.next, second.next = first. Advance prev to first and head to first.next for the next pair. Return dummyHead.next. This runs in O(n) time and O(1) space.

Why This Problem Matters

If basic linked list reversal is the "Hello World" of pointer manipulation, pairwise reversal is the next step up. It tests whether you can manage multiple pointer updates in the correct order without losing nodes. The dummy node technique you learn here is reusable across dozens of linked list problems, from merging sorted lists to removing duplicates. Nail this pattern and you will handle more complex linked list surgery with confidence.

Linked Lists: A Quick Refresher

A singly linked list is a chain of nodes where each node stores data and a reference to the next node. You can only traverse it from head to tail, one node at a time.

Key characteristics:

• Nodes: Each holds a value and a next pointer
• Head: Entry point to the list
• Tail: Last node, pointing to null
• Sequential access: No random indexing

Understanding the Problem

Given: The head of a singly linked list Task: Swap every two adjacent nodes in-place Return: The head of the modified list Constraints: O(n) time, O(1) space. The input list has 1 to 100 nodes.

Here is the transformation:

After pairwise reversal:

Notice that nodes swap in groups of two: (1,2) becomes (2,1), (3,4) becomes (4,3), and (5,6) becomes (6,5). The values stay with their nodes; only the links change.

Edge Cases

1. Empty list (null head): Return null
2. Single node: No pair to swap, return as-is
3. Two nodes: Simple single swap
4. Odd-length list: Last node stays in place

Solution Approach

The Dummy Node Technique

The key insight is that the head of the list changes after the first swap. To avoid writing special-case logic for the head, we introduce a dummy node that points to the original head. A prev pointer tracks the node immediately before the current pair, letting us stitch each swapped pair back into the list.

Think of it like rearranging train cars. The dummy node is a fixed anchor at the front. For each pair of cars, you detach them, swap their order, and reattach them to the anchor point before moving on to the next pair.

How One Swap Works

Let's trace the pointer reassignments for a single pair. Before the swap, the structure is: prev -> first -> second -> rest.

The three reassignments are:

1. prev.next = second - Link the predecessor to the second node
2. first.next = second.next - Connect the first node to whatever comes after the pair
3. second.next = first - Place the first node after the second

After these three steps, the pair is reversed: prev -> second -> first -> rest. Then we advance: prev = first and head = first.next.

Full Walkthrough

Let's trace the algorithm on [1, 2, 3, 4, 5, 6]:

Each iteration processes one pair and advances two nodes forward. After three iterations, every pair has been swapped.

Odd-Length Lists

When the list has an odd number of nodes, the loop terminates naturally because head.next is null for the last node:

The last node (5) has no partner, so it stays in place without any additional logic.

Implementation

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

public class Solution {
  public ListNode reverseInPairs(ListNode head) {
    ListNode dummyHead = new ListNode(-1);
    dummyHead.next = head;

    ListNode prev = dummyHead;

    while (head != null && head.next != null) {
      ListNode first = head, second = head.next;

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

      prev = first;
      head = first.next;
    }

    return dummyHead.next;
  }
}

Let's walk through this with [1, 2, 3, 4]:

Iteration 1:

• first = 1, second = 2
• prev.next = 2, 1.next = 3, 2.next = 1
• List: dummy -> 2 -> 1 -> 3 -> 4
• Advance: prev = 1, head = 3

Iteration 2:

• first = 3, second = 4
• prev.next = 4, 3.next = null, 4.next = 3
• List: dummy -> 2 -> 1 -> 4 -> 3
• Advance: prev = 3, head = null

Loop exits because head is null. Return dummyHead.next, which is node 2.

Complexity Analysis

Time Complexity: O(n)

The algorithm processes each node exactly once. In each iteration, it handles a pair of nodes with a constant number of pointer updates (three reassignments plus two advances). For a list of n nodes, there are n/2 iterations, giving O(n) total work.

Space Complexity: O(1)

Only a fixed set of pointer variables is used: dummyHead, prev, first, and second. No additional data structures are allocated, and the swap is performed in-place by rewiring existing nodes.

Alternative Approaches

1. Recursive: Swap the first pair, recursively process the rest. Clean code, but uses O(n) stack space.
2. Value swap: Swap the data values instead of the nodes. Simpler, but many interviewers explicitly forbid this because it doesn't test pointer manipulation.

The iterative dummy node approach is optimal for both time and space.

Common Pitfalls

1. Wrong pointer update order: If you set second.next = first before saving second.next, you lose the rest of the list.

   // Wrong order - rest of list is lost!
   second.next = first;         // Lost reference to node after second
   first.next = second.next;    // Now first.next = first (circular!)
   

2. Forgetting to update prev: After each swap, prev must move to first (which is now the second node in the swapped pair). Skipping this disconnects pairs from each other.

3. Not handling odd length: The while (head != null && head.next != null) condition naturally handles this. If you check only head != null, you will get a null pointer exception on head.next.

4. Returning the original head: After the first swap, the original head is no longer the first node. Always return dummyHead.next.

Interview Tips

1. Clarify the problem: "Should I swap node values or actually move the nodes?" Most interviewers want node movement.

2. Introduce the dummy node early: Mention that you are using a sentinel/dummy node to simplify head handling. This shows experience.

3. Draw the pointers: Sketch prev -> first -> second -> rest and show the three pointer updates. Visual learners (including most interviewers) will appreciate this.

4. State the order: Emphasize that the three pointer reassignments must happen in a specific order to avoid losing references.

5. Discuss follow-ups: "What if we needed to reverse in groups of K?" (a harder variant that uses the same dummy node technique with a more complex inner loop).

Key Takeaways

• The dummy node technique eliminates special-case logic for the head node and is reusable across many linked list problems.
• Each pair swap requires exactly three pointer reassignments in the correct order: link prev to second, link first to the rest, link second to first.
• The while (head != null && head.next != null) loop condition naturally handles both even and odd length lists without extra code.
• Always advance prev to first (not second) after each swap, because first is now the tail of the swapped pair and the predecessor of the next pair.
• Test with four cases: empty list, single node, two nodes, and an odd-length list. These cover every edge case the interviewer will ask about.

Practice

Pairwise reversal is one step along the linked list mastery path. Once you have it down, tackle these related challenges:

• Reverse a linked list (the simpler building block)
• Reverse nodes in groups of K (the generalized version)
• Check if a linked list is a palindrome (reverse the second half and compare)
• Swap Kth nodes from the beginning and end

Consistent practice is the key to interview success. This problem and hundreds more are available on Firecode, where over 50,000 developers have prepared for technical interviews and landed roles at top tech companies.

Happy coding, and may your pointers always land in pairs!

Solutions in Other Languages

Python

class Solution:
    def reverse_in_pairs(self, head):
        dummy_head = ListNode(-1)
        dummy_head.next = head

        prev = dummy_head

        while head is not None and head.next is not None:
            first, second = head, head.next

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

            prev = first
            head = first.next

        return dummy_head.next

JavaScript

class Solution {
  reverseInPairs(head) {
    const dummyHead = new ListNode(-1);
    dummyHead.next = head;

    let prev = dummyHead;

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

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

      prev = first;
      head = first.next;
    }

    return dummyHead.next;
  }
}

TypeScript

class Solution {
  reverseInPairs(head: ListNode | null): ListNode | null {
    const dummyHead = new ListNode(-1);
    dummyHead.next = head;

    let prev: ListNode = dummyHead;

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

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

      prev = first;
      head = first.next;
    }

    return dummyHead.next;
  }
}

C++

class Solution {
public:
  ListNode* reverseInPairs(ListNode* head) {
    ListNode dummyHead(-1, head);
    dummyHead.next = head;

    ListNode* prev = &dummyHead;

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

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

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

    return dummyHead.next;
  }
};

Go

func (s *Solution) ReverseInPairs(head *ListNode) *ListNode {
	dummyHead := &ListNode{Data: -1, Next: head}

	prev := dummyHead

	for head != nil && head.Next != nil {
		first, second := head, head.Next

		prev.Next = second
		first.Next = second.Next
		second.Next = first

		prev = first
		head = first.Next
	}

	return dummyHead.Next
}

Scala

class Solution {
  def reverseInPairs(head: ListNode): ListNode = {
    val dummyHead = new ListNode(-1)
    dummyHead.next = head

    var mutableHead = head

    var prev = dummyHead

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

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

      prev = first
      mutableHead = first.next
    }

    dummyHead.next
  }
}

Kotlin

class Solution {
    fun reverseInPairs(head: ListNode?): ListNode? {
        val dummyHead = ListNode(-1)
        dummyHead.next = head

        var prev = dummyHead

        var current = head

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

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

            prev = first
            current = first.next
        }

        return dummyHead.next
    }
}

Swift

class Solution {
    func reverseInPairs(_ head: ListNode?) -> ListNode? {
        let dummyHead = ListNode(-1)
        dummyHead.next = head

        var prev: ListNode = dummyHead

        var current = head

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

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

            prev = first
            current = first.next
        }

        return dummyHead.next
    }
}

Rust

impl Solution {
    pub fn reverse_in_pairs(&self, head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut dummy = Box::new(ListNode::new(-1));
        dummy.next = head;

        let mut prev = &mut dummy;

        while prev.next.is_some() && prev.next.as_ref().unwrap().next.is_some() {
            let mut first = prev.next.take().unwrap();
            let mut second = first.next.take().unwrap();

            first.next = second.next.take();
            second.next = Some(first);
            prev.next = Some(second);

            prev = prev.next.as_mut().unwrap().next.as_mut().unwrap();
        }

        dummy.next
    }
}

C#

public class Solution {
    public ListNode? ReverseInPairs(ListNode? head) {
        var dummyHead = new ListNode(-1);
        dummyHead.next = head;

        ListNode prev = dummyHead;

        while (head != null && head.next != null) {
            ListNode first = head, second = head.next;

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

            prev = first;
            head = first.next;
        }

        return dummyHead.next;
    }
}

Dart

class Solution {
  ListNode? reverseInPairs(ListNode? head) {
    ListNode dummyHead = ListNode(-1);
    dummyHead.next = head;

    ListNode? prev = dummyHead;

    while (head != null && head.next != null) {
      ListNode first = head;
      ListNode second = head.next!;

      prev!.next = second;
      first.next = second.next;
      second.next = first;

      prev = first;
      head = first.next;
    }

    return dummyHead.next;
  }
}

PHP

class Solution {
    public function reverseInPairs(?ListNode $head): ?ListNode {
        $dummyHead = new ListNode(-1);
        $dummyHead->next = $head;

        $prev = $dummyHead;

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

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

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

        return $dummyHead->next;
    }
}

Ruby

class Solution
  def reverse_in_pairs(head)
    dummy_head = ListNode.new(-1)
    dummy_head.next = head

    prev = dummy_head

    while head && head.next
      first, second = head, head.next

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

      prev = first
      head = first.next
    end

    dummy_head.next
  end
end