Swap Nodes in Pairs

Medium
2003.

Swap Nodes in Pairs

Swap Nodes in Pairs is a medium coding problem on recursion, asked in Amazon, Microsoft, Meta and Bloomberg interviews.

Given the head of a singly linked list, swap every two adjacent nodes — the 1st with the 2nd, the 3rd with the 4th, and so on — and return the head of the new list. A last node without a partner stays where it is.

Change the links, not the values: the nodes themselves must move.

Example 1

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

Example 2

Input
head = []
Output
[]

Example 3

Input
head = [1,2,3]
Output
[2,1,3]
Explanation
Node 3 has no partner and keeps its place.

Constraints

  • The number of nodes in the list is in the range [0, 100]
  • 0 <= Node.val <= 100
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * Definition for singly-linked list (provided by the judge — do not redefine it):
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var swapPairs = function(head) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Swap Nodes in Pairs — Solution in Python, Java & C++

Swap Nodes in Pairs solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on recursion.

Swap Nodes in Pairs is a medium coding problem on recursion, asked in Amazon, Microsoft, Meta and Bloomberg interviews.

  • Difficulty: Medium
  • Topics: Recursion
  • Asked at: Amazon, Microsoft, Meta, Bloomberg
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given the head of a singly linked list, swap every two adjacent nodes — the 1st with the 2nd, the 3rd with the 4th, and so on — and return the head of the new list. A last node without a partner stays where it is.

Change the links, not the values: the nodes themselves must move.

Example 1

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

Example 2

Input: head = []
Output: []

Example 3

Input: head = [1,2,3]
Output: [2,1,3]
Explanation: Node 3 has no partner and keeps its place.

Constraints

  • The number of nodes in the list is in the range [0, 100]
  • 0 <= Node.val <= 100

Hints for Swap Nodes in Pairs

  1. Hint 1

    Work on one pair at a time: the pair (a, b) that follows some node prev becomes (b, a).

  2. Hint 2

    Three links change per pair: prev.next = b, a.next = b.next, b.next = a.

  3. Hint 3

    Then a is the node before the next pair. A dummy node before the head plays prev for the first pair.

How to solve Swap Nodes in Pairs

Walk the list pair by pair, keeping the node before each pair. Swapping a pair is three link changes, and the first node of the old pair ends up as the predecessor of the next one.

Approach

  1. Create a dummy node pointing at head; set prev = dummy.
  2. While prev.next and prev.next.next exist: let a = prev.next, b = a.next.
  3. Relink: a.next = b.next, b.next = a, prev.next = b.
  4. Move on with prev = a.
  5. Return dummy.next.

Why it works

Each iteration turns prev → a → b → rest into prev → b → a → rest, touching nothing else, and leaves prev before rest. The loop stops when fewer than two nodes remain, which leaves an odd last node untouched.

Complexity

  • Time — O(n)
  • Space — O(1) iteratively (the recursive version uses O(n) stack)

Pitfalls

  • Order the three assignments so no link is lost: save b.next (via a.next = b.next) before overwriting b.next.
  • Swapping values instead of nodes defeats the exercise.
  • Both the empty list and a single node must come back unchanged.

Reference solution

Python

from typing import Optional

def swapPairs(head: Optional[ListNode]) -> Optional[ListNode]:
    dummy = ListNode(0, head)
    prev = dummy
    while prev.next and prev.next.next:
        a = prev.next
        b = a.next
        a.next = b.next
        b.next = a
        prev.next = b
        prev = a
    return dummy.next

Java

public static ListNode swapPairs(ListNode head) {
    ListNode dummy = new ListNode(0, head), prev = dummy;
    while (prev.next != null && prev.next.next != null) {
        ListNode a = prev.next, b = a.next;
        a.next = b.next;
        b.next = a;
        prev.next = b;
        prev = a;
    }
    return dummy.next;
}

C++

ListNode* swapPairs(ListNode* head) {
    ListNode dummy(0, head);
    ListNode* prev = &dummy;
    while (prev->next && prev->next->next) {
        ListNode* a = prev->next;
        ListNode* b = a->next;
        a->next = b->next;
        b->next = a;
        prev->next = b;
        prev = a;
    }
    return dummy.next;
}

JavaScript

var swapPairs = function(head) {
    var dummy = new ListNode(0, head), prev = dummy;
    while (prev.next !== null && prev.next.next !== null) {
        var a = prev.next, b = a.next;
        a.next = b.next;
        b.next = a;
        prev.next = b;
        prev = a;
    }
    return dummy.next;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 40 recursion problems · the whole catalogue

Learn the technique: Recursion