Log inSign up
mediumLeetCodeNot Started

Swap Nodes in Pairs

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Linked List
Solve on LeetCode
Lesson

Problem Statement

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list's nodes (i.e., only nodes themselves may be changed.)

Example 1:

Input: head = [1,2,3,4]
Output: [2,1,4,3]
Explanation: Pairs (1, 2) and (3, 4) are swapped into (2, 1) and (4, 3).

Example 2:

Input: head = []
Output: []
Explanation: Empty list produces empty list.

Example 3:

Input: head = [1]
Output: [1]
Explanation: Single node cannot be paired, remains unchanged.

Constraints:

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

1. Array Value Swapping (Naive Value Modification)

Intuition

1. Collect node values into a vector/list. 2. Iterate through indices i = 0, 2, 4, ... < len - 1 and swap vals[i] with vals[i + 1]. 3. Traverse linked list and overwrite node values with the swapped array.

When to apply: Quick conceptual demonstration (note: many interviewers forbid value swapping and require node pointer mutation).

Algorithm

  1. Traverse linked list and append values to array.
  2. Swap values in adjacent pairs in array.
  3. Write swapped values back into linked list nodes.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5struct ListNode {
6 int val;
7 ListNode *next;
8 ListNode() : val(0), next(nullptr) {}
9 ListNode(int x) : val(x), next(nullptr) {}
10 ListNode(int x, ListNode *next) : val(x), next(next) {}
11};
12
13class Solution {
14public:
15 ListNode* swapPairs(ListNode* head) {
16 if (!head || !head->next) return head;
17
18 std::vector<int> vals;
19 ListNode* curr = head;
20 while (curr != nullptr) {
21 vals.push_back(curr->val);
22 curr = curr->next;
23 }
24
25 for (size_t i = 0; i + 1 < vals.size(); i += 2) {
26 std::swap(vals[i], vals[i + 1]);
27 }
28
29 curr = head;
30 for (int v : vals) {
31 curr->val = v;
32 curr = curr->next;
33 }
34 return head;
35 }
36};
37
38int main() {
39 ListNode* head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4))));
40 Solution sol;
41 ListNode* res = sol.swapPairs(head);
42 while (res != nullptr) {
43 std::cout << res->val << " ";
44 res = res->next;
45 }
46 std::cout << std::endl;
47 return 0;
48}

Time & Space Complexity

  • Time complexity: O(N) — Extracting, swapping in array, and rewriting values each take O(N) operations.
  • Space complexity: O(N) — Requires O(N) auxiliary array space.

2. Recursive Pairwise Pointer Swap

Intuition

1. Base case: If head == null || head.next == null, return head. 2. Let first = head, second = head.next. 3. Recursive step: first.next = swapPairs(second.next). 4. Link second to first: second.next = first. 5. Return second as the head of the swapped sublist.

When to apply: Clean, highly expressive functional/recursive solution.

Algorithm

  1. Base case: return head if 0 or 1 node remains.
  2. Store references to first and second nodes of current pair.
  3. Set first.next = swapPairs(second.next).
  4. Set second.next = first.
  5. Return second.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct ListNode {
4 int val;
5 ListNode *next;
6 ListNode() : val(0), next(nullptr) {}
7 ListNode(int x) : val(x), next(nullptr) {}
8 ListNode(int x, ListNode *next) : val(x), next(next) {}
9};
10
11class Solution {
12public:
13 ListNode* swapPairs(ListNode* head) {
14 if (!head || !head->next) return head;
15
16 ListNode* first = head;
17 ListNode* second = head->next;
18
19 first->next = swapPairs(second->next);
20 second->next = first;
21
22 return second;
23 }
24};
25
26int main() {
27 ListNode* head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4))));
28 Solution sol;
29 ListNode* res = sol.swapPairs(head);
30 while (res != nullptr) {
31 std::cout << res->val << " ";
32 res = res->next;
33 }
34 std::cout << std::endl;
35 return 0;
36}

Time & Space Complexity

  • Time complexity: O(N) — Visits every node once: O(N) linear time.
  • Space complexity: O(N) call stack — Consumes N/2 stack frames for list of length N, resulting in O(N) space.

3. Iterative In-Place Pairwise Swap with Dummy Sentinel

Intuition

1. Initialize dummy node dummy with dummy.next = head. 2. Initialize prev = dummy. 3. While prev.next != null && prev.next.next != null: - first = prev.next - second = prev.next.next - first.next = second.next - second.next = first - prev.next = second - prev = first 4. Return dummy.next.

When to apply: The definitive, optimal O(N) time and O(1) auxiliary space solution demanded in interviews.

Algorithm

  1. Initialize dummy pointing to head, prev = dummy.
  2. While at least two nodes follow prev:
  3. - Let first = prev.next, second = prev.next.next.
  4. - Point first.next to second.next.
  5. - Point second.next to first.
  6. - Point prev.next to second.
  7. - Advance prev = first.
  8. Return dummy.next.

Linked List Interactive Dry Run

2 of 2 questions left today
Step 1 / 4
Trace timeline25% explored
Current operationSTEP 1 OF 4
Rewire pointers: node 1
Visual state
Values and pointers at this exact step
linked list
This linked list trace has no visual items for the current step yet. Add step.items (and connections where needed) to render its structure accurately.
Why this step matters

Rewire pointers: node 1.next = node 3, node 2.next = node 1, dummy.next = node 2.

Step 1 / 4
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2
3struct ListNode {
4 int val;
5 ListNode *next;
6 ListNode() : val(0), next(nullptr) {}
7 ListNode(int x) : val(x), next(nullptr) {}
8 ListNode(int x, ListNode *next) : val(x), next(next) {}
9};
10
11class Solution {
12public:
13 ListNode* swapPairs(ListNode* head) {
14 ListNode dummy(0, head);
15 ListNode* prev = &dummy;
16
17 while (prev->next != nullptr && prev->next->next != nullptr) {
18 ListNode* first = prev->next;
19 ListNode* second = prev->next->next;
20
21 first->next = second->next;
22 second->next = first;
23 prev->next = second;
24
25 prev = first;
26 }
27
28 return dummy.next;
29 }
30};
31
32int main() {
33 ListNode* head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4))));
34 Solution sol;
35 ListNode* res = sol.swapPairs(head);
36 while (res != nullptr) {
37 std::cout << res->val << " ";
38 res = res->next;
39 }
40 std::cout << std::endl;
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(N) — Processes two nodes per loop iteration, traversing the entire list in N/2 steps: O(N) time.
  • Space complexity: O(1) auxiliary — Only requires four local pointer variables (dummy, prev, first, second): strictly O(1) auxiliary memory.

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Array Value Swapping (Naive Value Modification)O(N)O(N)Extract values into an array, swap adjacent values vals[i] and vals[i+1], and write them back into the nodes.High time complexity
2.Recursive Pairwise Pointer SwapO(N)O(N) call stackRecursively swap nodes pair by pair. The second node becomes the new head of the pair, its next points to the first node, and first node's next points to the recursive call on the third node.—
3.Iterative In-Place Pairwise Swap with Dummy SentinelOptimalO(N)O(1) auxiliaryAnchor pointer prev at a dummy sentinel node. In each step, swap first = prev.next and second = prev.next.next by rewiring 3 pointers in O(1) space.—

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Mutating node.val instead of pointer rewiring: this violates the problem constraint and interview standards.

Pitfall 2:

Setting prev = second instead of prev = first: since first was swapped to the second position, first is the actual tail of the pair.

Pitfall 3:

Forgetting dummy head, creating unnecessary edge cases for head modification.

Back to DSA Sheet