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:
[0, 100].0 <= Node.val <= 100Problem Overview: Given the head of a singly linked list, swap every two adjacent nodes and return the modified list. Node values cannot be changed; only pointers may be rearranged.
Approach 1: Iterative Pointer Manipulation (O(n) time, O(1) space)
This approach walks through the list and swaps nodes in pairs using pointer updates. You maintain a dummy node before the head so the first swap is handled cleanly. For each pair (first, second), update three links: connect the previous node to second, point first to the node after the pair, then link second to first. Move the pointer forward by two nodes and repeat until fewer than two nodes remain. The algorithm only rearranges references, so it runs in O(n) time with O(1) extra space and is the most common pattern used in linked list pointer problems.
Approach 2: Recursive Pair Swapping (O(n) time, O(n) space)
The recursive solution treats each pair as a small subproblem. If the list is empty or has only one node, return it directly. Otherwise, identify the first two nodes, swap them, and recursively process the rest of the list starting from the third node. After the recursive call returns the head of the processed remainder, connect the first node of the current pair to that result. Each call handles exactly one pair, giving a clean and expressive solution built on recursion. The runtime is O(n) since every node is visited once, but the call stack adds O(n) auxiliary space.
Recommended for interviews: The iterative pointer approach is typically expected in interviews. It demonstrates strong understanding of pointer manipulation in linked list structures and achieves constant extra space. The recursive method is shorter and easier to reason about but uses additional stack memory. Showing the iterative version signals that you can manage pointer updates carefully, which is a core skill for linked list problems.
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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
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 | 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. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Pointer Manipulation | O(n) | O(1) | Best general solution. Preferred in interviews and production code due to constant space. |
| Recursive Pair Swapping | O(n) | O(n) | Useful when recursion is allowed and code clarity is prioritized over stack usage. |
Swap Nodes in Pairs - Apple Interview Question - Leetcode 24 • NeetCode • 73,215 views views
Watch 9 more video solutions →Practice Swap Nodes in Pairs with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor