Pairwise Swap Nodes in a Linked List

Medium15–20 min

Topics

Linked ListReversal

Companies

AmazonMicrosoftAdobeGoogle

Given the head of a singly linked list, swap every two adjacent nodes and return the new head. Nodes must actually be relinked, not just have their values swapped — a leftover single node (odd-length list) stays exactly where it is. The optimal solution anchors a prev pointer right before each pair with a dummy node, exactly the same idea used to reverse any run of nodes: relink first.next, second.next, and prev.next in a fixed three-line sequence so second ends up leading and first trails right behind it, then slide prev up to first — now the trailing node of the pair just swapped — before repeating for the next pair.

Test Case 1:

Input:head = [1, 2, 3, 4]

Output:[2, 1, 4, 3]

Explanation:Each adjacent pair swaps places.

Test Case 2:

Input:head = []

Output:[]

Explanation:An empty list has nothing to swap.

Test Case 3:

Input:head = [1]

Output:[1]

Explanation:A single node has no partner, so it's untouched.

Constraints

◆0 ≤ number of nodes in head ≤ 200
◆-1000 ≤ node value ≤ 1000

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

head (list values) — 1-8 integers

1	class Solution {
2	public Node swapPairs(Node head) {
3	Node dummy = new Node(0);
4	dummy.next = head;
5	Node prev = dummy;
6	while (prev.next != null && prev.next.next != null) {
7	Node first = prev.next;
8	Node second = first.next;
9	first.next = second.next;
10	second.next = first;
11	prev.next = second;
12	prev = first;
13	}
14	return dummy.next;
15	}
16	}
17

null

Variables

prevdummy

INITIALIZE

A dummy node lets the very first pair be swapped the same way as every later one. prev starts at dummy.

Step 1 / 17

Approach & Solutions

Brute Force — Collect Values, Swap Adjacent Pairs, Write Back

Good

Copy every value into an array, swap each adjacent pair of array entries, then walk the list once more overwriting .val in that swapped order. This never touches a single .next pointer — it's correct, but it costs an array the size of the whole list where the optimal solution needs none.

TimeO(n)

SpaceO(n)

Java

Try it out

// Node definition used in this problem:
// class Node {
//     int val;
//     Node next;
// }

class Solution {
    public Node swapPairs(Node head) {
        List<Integer> vals = new ArrayList<>();
        Node curr = head;
        while (curr != null) {
            vals.add(curr.val);
            curr = curr.next;
        }
        int i = 0;
        while (i + 1 < vals.size()) {
            int temp = vals.get(i);
            vals.set(i, vals.get(i + 1));
            vals.set(i + 1, temp);
            i += 2;
        }
        curr = head;
        for (int v : vals) {
            curr.val = v;
            curr = curr.next;
        }
        return head;
    }
}

Optimal — Swap Pairs by Relinking, Not by Value

Optimal

A dummy node lets the very first pair swap the same way as every later one. For each pair: first is prev's next node, second is first's next. Relink so second comes before first — first.next skips over second, second.next points at first, and prev.next points at second — then move prev up to first, which is now the trailing node of the pair just swapped, ready to anchor the next one. No new nodes, no extra memory.