24. Swap Nodes In Pairs - Explanation

Description

Swap the first two nodes of the singly linked list, then the next two nodes, and continue pair by pair. Return the new head. If the list has an odd number of nodes, leave the final node in place. Change the links between nodes rather than changing the values stored in them. Arrays in the examples and test inputs show node values from head to tail; [] represents an empty list.

Example 1:

Swap Nodes in Pairs, example 1: illustration of the example

Input: head = [4,7,2,9]

Output: [7,4,9,2]

Explanation: Swap the nodes containing 4 and 7, then swap the nodes containing 2 and 9. The resulting chain is 7 -> 4 -> 9 -> 2.

Example 2:

Swap Nodes in Pairs, example 2: illustration of the example

Input: head = [8,3,5]

Output: [3,8,5]

Explanation: Swap the first pair, containing 8 and 3. The final node containing 5 has no partner and stays at the end.

Example 3:

Swap Nodes in Pairs, example 3: illustration of the example

Input: head = []

Output: []

Explanation: An empty list has no pairs to swap, so return an empty list.

Constraints:

The list contains between 0 and 100 nodes.
0 <= Node.val <= 100
Swap nodes by changing links; do not modify node values.

Topics

Linked List Recursion

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Linked List Fundamentals - Understanding node structure, traversal, and pointer manipulation in singly linked lists
In-Place Pointer Manipulation - Reversing or reordering nodes by changing next pointers without extra data structures
Dummy Node Technique - Using a sentinel node to simplify edge cases when the head of the list changes

1. Convert To Array

Intuition

The simplest approach is to convert the linked list to an array, where swapping elements is straightforward using index-based access. Once we swap adjacent elements in the array, we rebuild the linked list connections. This trades space efficiency for implementation simplicity.

Algorithm

Traverse the linked list and store all nodes in an array.
Iterate through the array in steps of 2, swapping adjacent elements.
Reconnect all nodes by setting each node's next pointer to the following node in the array.
Set the last node's next to null and return the first element as the new head.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head:
            return None
        arr = []
        cur = head

        while cur:
            arr.append(cur)
            cur = cur.next

        for i in range(0, len(arr) - 1, 2):
            arr[i], arr[i + 1] = arr[i + 1], arr[i]

        for i in range(len(arr) - 1):
            arr[i].next = arr[i + 1]

        arr[-1].next = None
        return arr[0]

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null) return null;

        List<ListNode> arr = new ArrayList<>();
        ListNode cur = head;

        while (cur != null) {
            arr.add(cur);
            cur = cur.next;
        }

        for (int i = 0; i < arr.size() - 1; i += 2) {
            ListNode temp = arr.get(i);
            arr.set(i, arr.get(i + 1));
            arr.set(i + 1, temp);
        }

        for (int i = 0; i < arr.size() - 1; i++) {
            arr.get(i).next = arr.get(i + 1);
        }

        arr.get(arr.size() - 1).next = null;
        return arr.get(0);
    }
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head) return nullptr;

        vector<ListNode*> arr;
        ListNode* cur = head;

        while (cur) {
            arr.push_back(cur);
            cur = cur->next;
        }

        for (size_t i = 0; i + 1 < arr.size(); i += 2) {
            swap(arr[i], arr[i + 1]);
        }

        for (size_t i = 0; i + 1 < arr.size(); i++) {
            arr[i]->next = arr[i + 1];
        }

        arr.back()->next = nullptr;
        return arr[0];
    }
};

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     constructor(val = 0, next = null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
class Solution {
    /**
     * @param {ListNode} head
     * @return {ListNode}
     */
    swapPairs(head) {
        if (!head) return null;

        let arr = [];
        let cur = head;

        while (cur) {
            arr.push(cur);
            cur = cur.next;
        }

        for (let i = 0; i + 1 < arr.length; i += 2) {
            [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
        }

        for (let i = 0; i + 1 < arr.length; i++) {
            arr[i].next = arr[i + 1];
        }

        arr[arr.length - 1].next = null;
        return arr[0];
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode SwapPairs(ListNode head) {
        if (head == null) return null;

        var arr = new List<ListNode>();
        var cur = head;

        while (cur != null) {
            arr.Add(cur);
            cur = cur.next;
        }

        for (int i = 0; i + 1 < arr.Count; i += 2) {
            (arr[i], arr[i + 1]) = (arr[i + 1], arr[i]);
        }

        for (int i = 0; i + 1 < arr.Count; i++) {
            arr[i].next = arr[i + 1];
        }

        arr[arr.Count - 1].next = null;
        return arr[0];
    }
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }

    arr := []*ListNode{}
    cur := head

    for cur != nil {
        arr = append(arr, cur)
        cur = cur.Next
    }

    for i := 0; i+1 < len(arr); i += 2 {
        arr[i], arr[i+1] = arr[i+1], arr[i]
    }

    for i := 0; i+1 < len(arr); i++ {
        arr[i].Next = arr[i+1]
    }

    arr[len(arr)-1].Next = nil
    return arr[0]
}

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun swapPairs(head: ListNode?): ListNode? {
        if (head == null) return null

        val arr = mutableListOf<ListNode>()
        var cur = head

        while (cur != null) {
            arr.add(cur)
            cur = cur.next
        }

        var i = 0
        while (i + 1 < arr.size) {
            val temp = arr[i]
            arr[i] = arr[i + 1]
            arr[i + 1] = temp
            i += 2
        }

        for (j in 0 until arr.size - 1) {
            arr[j].next = arr[j + 1]
        }

        arr[arr.size - 1].next = null
        return arr[0]
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func swapPairs(_ head: ListNode?) -> ListNode? {
        guard let head = head else { return nil }

        var arr = [ListNode]()
        var cur: ListNode? = head

        while let node = cur {
            arr.append(node)
            cur = node.next
        }

        var i = 0
        while i + 1 < arr.count {
            arr.swapAt(i, i + 1)
            i += 2
        }

        for j in 0..<(arr.count - 1) {
            arr[j].next = arr[j + 1]
        }

        arr[arr.count - 1].next = nil
        return arr[0]
    }
}

impl Solution {
    pub fn swap_pairs(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut arr: Vec<Box<ListNode>> = Vec::new();
        let mut cur = head;

        while let Some(mut node) = cur {
            cur = node.next.take();
            arr.push(node);
        }

        if arr.is_empty() {
            return None;
        }

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

        let mut i = arr.len() - 1;
        let mut result = Some(arr.pop().unwrap());
        while let Some(mut node) = arr.pop() {
            node.next = result;
            result = Some(node);
        }

        result
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

2. Recursion

Intuition

We can think of the problem recursively: swap the first two nodes, then let recursion handle the rest. The first node should point to the result of swapping the remaining list (starting from the third node). The second node becomes the new head of this pair and points to the first node. This recursive structure naturally handles lists of any length.

Algorithm

Base case: if the list is empty or has only one node, return the head as-is.
Save references to the first node (cur) and second node (nxt).
Recursively swap the sublist starting from the third node and connect it to cur.
Point nxt to cur.
Return nxt as the new head of this swapped pair.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head

        cur = head
        nxt = head.next
        cur.next = self.swapPairs(nxt.next)
        nxt.next = cur
        return nxt

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode cur = head;
        ListNode nxt = head.next;
        cur.next = swapPairs(nxt.next);
        nxt.next = cur;

        return nxt;
    }
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }

        ListNode* cur = head;
        ListNode* nxt = head->next;
        cur->next = swapPairs(nxt->next);
        nxt->next = cur;

        return nxt;
    }
};

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     constructor(val = 0, next = null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
class Solution {
    /**
     * @param {ListNode} head
     * @return {ListNode}
     */
    swapPairs(head) {
        if (!head || !head.next) {
            return head;
        }

        let cur = head;
        let nxt = head.next;
        cur.next = this.swapPairs(nxt.next);
        nxt.next = cur;

        return nxt;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode SwapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode cur = head;
        ListNode nxt = head.next;
        cur.next = SwapPairs(nxt.next);
        nxt.next = cur;

        return nxt;
    }
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    cur := head
    nxt := head.Next
    cur.Next = swapPairs(nxt.Next)
    nxt.Next = cur

    return nxt
}

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun swapPairs(head: ListNode?): ListNode? {
        if (head == null || head.next == null) {
            return head
        }

        val cur = head
        val nxt = head.next
        cur.next = swapPairs(nxt?.next)
        nxt?.next = cur

        return nxt
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func swapPairs(_ head: ListNode?) -> ListNode? {
        if head == nil || head?.next == nil {
            return head
        }

        let cur = head
        let nxt = head?.next
        cur?.next = swapPairs(nxt?.next)
        nxt?.next = cur

        return nxt
    }
}

impl Solution {
    pub fn swap_pairs(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        match head {
            None => None,
            Some(mut cur) => {
                match cur.next.take() {
                    None => Some(cur),
                    Some(mut nxt) => {
                        cur.next = Self::swap_pairs(nxt.next.take());
                        nxt.next = Some(cur);
                        Some(nxt)
                    }
                }
            }
        }
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$ for recursion stack.

3. Iteration

Intuition

We can swap pairs in place by carefully managing pointers. A dummy node simplifies handling the head change. For each pair, we need to: save the reference to the next pair, reverse the current pair's pointers, and connect the previous node to the new first node of the swapped pair. Moving two nodes at a time ensures we process each pair exactly once.

Algorithm

Create a dummy node pointing to the head, and initialize prev to dummy and curr to head.
While curr and curr.next both exist:
- Save the start of the next pair: nxtPair = curr.next.next.
- Identify the second node in the pair.
- Reverse the pair: point second to first, first to the next pair.
- Connect previous node to the new first (second node).
- Update prev to be curr and move curr to nxtPair.
Return dummy.next.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        prev, curr = dummy, head

        while curr and curr.next:
            nxtPair = curr.next.next
            second = curr.next

            # Reverse this pair
            second.next = curr
            curr.next = nxtPair
            prev.next = second

            # Update pointers
            prev = curr
            curr = nxtPair

        return dummy.next

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
public class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy, curr = head;

        while (curr != null && curr.next != null) {
            ListNode nxtPair = curr.next.next;
            ListNode second = curr.next;

            // Reverse this pair
            second.next = curr;
            curr.next = nxtPair;
            prev.next = second;

            // Update pointers
            prev = curr;
            curr = nxtPair;
        }

        return dummy.next;
    }
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode dummy(0, head);
        ListNode* prev = &dummy, *curr = head;

        while (curr && curr->next) {
            ListNode* nxtPair = curr->next->next;
            ListNode* second = curr->next;

            // Reverse this pair
            second->next = curr;
            curr->next = nxtPair;
            prev->next = second;

            // Update pointers
            prev = curr;
            curr = nxtPair;
        }

        return dummy.next;
    }
};

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     constructor(val = 0, next = null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
class Solution {
    /**
     * @param {ListNode} head
     * @return {ListNode}
     */
    swapPairs(head) {
        let dummy = new ListNode(0, head);
        let prev = dummy,
            curr = head;

        while (curr && curr.next) {
            let nxtPair = curr.next.next;
            let second = curr.next;

            // Reverse this pair
            second.next = curr;
            curr.next = nxtPair;
            prev.next = second;

            // Update pointers
            prev = curr;
            curr = nxtPair;
        }

        return dummy.next;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
public class Solution {
    public ListNode SwapPairs(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode prev = dummy, curr = head;

        while (curr != null && curr.next != null) {
            ListNode nxtPair = curr.next.next;
            ListNode second = curr.next;

            // Reverse this pair
            second.next = curr;
            curr.next = nxtPair;
            prev.next = second;

            // Update pointers
            prev = curr;
            curr = nxtPair;
        }

        return dummy.next;
    }
}

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func swapPairs(head *ListNode) *ListNode {
    dummy := &ListNode{Val: 0, Next: head}
    prev, curr := dummy, head

    for curr != nil && curr.Next != nil {
        nxtPair := curr.Next.Next
        second := curr.Next

        // Reverse this pair
        second.Next = curr
        curr.Next = nxtPair
        prev.Next = second

        // Update pointers
        prev = curr
        curr = nxtPair
    }

    return dummy.Next
}

/**
 * Example:
 * var li = ListNode(5)
 * var v = li.`val`
 * Definition for singly-linked list.
 * class ListNode(var `val`: Int) {
 *     var next: ListNode? = null
 * }
 */
class Solution {
    fun swapPairs(head: ListNode?): ListNode? {
        val dummy = ListNode(0).apply { next = head }
        var prev: ListNode? = dummy
        var curr = head

        while (curr != null && curr.next != null) {
            val nxtPair = curr.next?.next
            val second = curr.next

            // Reverse this pair
            second?.next = curr
            curr.next = nxtPair
            prev?.next = second

            // Update pointers
            prev = curr
            curr = nxtPair
        }

        return dummy.next
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public var val: Int
 *     public var next: ListNode?
 *     public init() { self.val = 0; self.next = nil; }
 *     public init(_ val: Int) { self.val = val; self.next = nil; }
 *     public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
 * }
 */
class Solution {
    func swapPairs(_ head: ListNode?) -> ListNode? {
        let dummy = ListNode(0, head)
        var prev: ListNode? = dummy
        var curr = head

        while curr != nil && curr?.next != nil {
            let nxtPair = curr?.next?.next
            let second = curr?.next

            // Reverse this pair
            second?.next = curr
            curr?.next = nxtPair
            prev?.next = second

            // Update pointers
            prev = curr
            curr = nxtPair
        }

        return dummy.next
    }
}

impl Solution {
    pub fn swap_pairs(head: Option<Box<ListNode>>) -> Option<Box<ListNode>> {
        let mut dummy = Box::new(ListNode { val: 0, 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();
            let rest = second.next.take();

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

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

        dummy.next
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Losing Reference to the Next Pair

When swapping a pair of nodes, you must save a reference to the node after the pair (curr.next.next) before modifying any pointers. If you swap the current pair first, curr.next changes and you lose access to the remaining list. Always store nxtPair = curr.next.next at the beginning of each iteration.

Forgetting to Update the Previous Node's Next Pointer

After swapping a pair, the previous node (or dummy node for the first pair) must point to the new first node of the swapped pair. A common mistake is correctly swapping the pair internally but failing to connect it back to the rest of the list, resulting in a broken chain or lost nodes.

Not Handling Odd-Length Lists

When the list has an odd number of nodes, the last node has no partner to swap with and should remain in place. Your loop condition must check that both curr and curr.next exist before attempting a swap. Failing to check both conditions can cause null pointer exceptions or incorrect behavior on the final unpaired node.