Swap Nodes in Pairs - Solution & Explanation
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:
Example 2:
Input: head = []
Output: []
Example 3:
Input: head = [1]
Output: [1]
Example 4:
Input: head = [1,2,3]
Output: [2,1,3]
Constraints:
- The number of nodes in the list is in the range
[0, 100]. 0 <= Node.val <= 100
Approach Overview
Problem Overview: You receive the head of a singly linked list and must swap every two adjacent nodes. The swap must change node pointers, not node values. For example, 1→2→3→4 becomes 2→1→4→3. If the list length is odd, the final node remains unchanged.
Approach 1: Iterative Pointer Manipulation (O(n) time, O(1) space)
This approach walks through the list while swapping nodes in pairs using pointer updates. Maintain a dummy node before the head to simplify edge handling. For each pair, identify first and second, then update three pointers: connect the previous node to second, point first.next to the node after the pair, and set second.next to first. Move the pointer forward by two nodes and repeat. Every node is visited once, giving O(n) time with constant extra memory O(1). This is the most practical technique when working with linked list pointer manipulation.
Approach 2: Recursive Pair Swapping (O(n) time, O(n) space)
The recursive solution treats the list as a sequence of pairs. The base case occurs when the list has zero or one node remaining. For each recursive call, swap the first two nodes: let second become the new head of the pair, then recursively process the remaining list starting from head.next.next. After the recursive call returns, attach the result to head.next. Each call processes exactly one pair, so the algorithm still runs in O(n) time. The recursion stack stores up to n/2 calls, resulting in O(n) auxiliary space. This version highlights structural thinking often used in recursion problems involving linked structures.
Recommended for interviews: The iterative pointer solution is usually the expected answer. Interviewers want to see that you can safely manipulate linked list pointers without breaking the chain. The recursive version demonstrates good conceptual understanding of pairwise decomposition, but the iterative approach is preferred because it avoids stack overhead and keeps space complexity at O(1).
Approach 1: Iterative Approach
This approach uses iteration to systematically swap each pair of adjacent nodes in the linked list. The main idea is to traverse the list while keeping track of pointers to the nodes before and after the pair being swapped. By adjusting these pointers, we effectively swap nodes without modifying their values.
The solution uses a dummy node to handle edge cases smoothly, such as when the list has less than two nodes. The dummy node is set at the beginning before the head. We iterate through the list while there are at least two nodes to swap.
We store references to the nodes to be swapped (a and b), rearrange the pointers to complete the swap, and finally, move the prev pointer to the current a, setting up for the next iteration.
Complexity
Time Complexity: O(n), where n is the number of nodes in the linked list. We process each node once.
Space Complexity: O(1), We are using constant extra space.
Approach 2: Recursive Approach
This approach leverages recursion to swap every two adjacent nodes. The key idea is to break the problem into subproblems where you solve for a pair and recursively call to solve for the next. The recursion naturally handles the base case where less than two nodes remain to be swapped.
The C implementation uses recursion to address each swap operation. The function swaps the first two nodes and then invokes itself on the remaining list. It continues until it reaches a list with zero or one node, at which point it returns the node itself. This effectively builds the solution from back to front on the call stack, as the reversed remaining pairs are linked to complete the swaps.
Complexity
Time Complexity: O(n), every node is processed once.
Space Complexity: O(n), the call stack in recursive functions uses space proportional to the number of elements.
Approach 3: Recursion
We can implement swapping two nodes in the linked list through recursion.
The termination condition of recursion is that there are no nodes in the linked list, or there is only one node in the linked list. At this time, swapping cannot be performed, so we directly return this node.
Otherwise, we recursively swap the linked list head.next.next, and let the swapped head node be t. Then we let p be the next node of head, and let p point to head, and head point to t, finally return p.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the linked list.
Code
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
Ruby
Approach 4: Iteration
We set a dummy head node dummy, initially pointing to head, and then set two pointers pre and cur, initially pre points to dummy, and cur points to head.
Next, we traverse the linked list. Each time we need to swap the two nodes after pre, so we first judge whether cur and cur.next are empty. If they are not empty, we perform the swap, otherwise we terminate the loop.
The time complexity is O(n), and the space complexity is O(1). Here, n is the length of the linked list.
Code
Python
Java
C++
Go
TypeScript
JavaScript
C#
PHP
Complexity Comparison
| Approach | Complexity |
|---|---|
| Iterative Approach | Time Complexity: O(n), where n is the number of nodes in the linked list. We process each node once. Space Complexity: O(1), We are using constant extra space. |
| Recursive Approach | Time Complexity: O(n), every node is processed once. Space Complexity: O(n), the call stack in recursive functions uses space proportional to the number of elements. |
| Recursion | — |
| Iteration | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Pointer Manipulation | O(n) | O(1) | Best general solution; efficient pointer updates without recursion |
| Recursive Pair Swapping | O(n) | O(n) | Useful for practicing recursive reasoning on linked list structures |
Video Solution
Swap Nodes in Pairs - Apple Interview Question - Leetcode 24 • NeetCode • 89,077 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Swap Nodes in Pairs easy or hard?
How to solve Swap Nodes in Pairs in O(n)?
Swap Nodes in Pairs Python or Java solution
What is the best approach for Swap Nodes in Pairs?
Is Swap Nodes in Pairs asked at Google Amazon Meta?
What data structure is used in Swap Nodes in Pairs?
What is the time complexity of Swap Nodes in Pairs?
Ready to solve this problem?
Practice Swap Nodes in Pairs with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor