Swap Nodes in Pairs
Problem Description
Question
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]
1
2
3
4
null
Output:[2,1,4,3]
2
1
4
3
null
Example 2:
Input:head=[]
null
Output:[]
null
Example 3:
Input:head=[1]
1
null
Output:[1]
1
null
Example 3:
Input:head=[1,2,3]
0
1
1
2
2
3
Output:[2,1,3]
2
1
3
null
Constraints:
- The number of nodes in the list is in the range
[0, 100]. 0 <= Node.val <= 100
Solve it on LeetCode
Approaches
1. Recursive Approach
The recursive approach involves swapping nodes in pairs and continues until the end of the linked list is reached. Here's the idea:
- Base Case: If the list is empty or has only one node, no swap is needed. Return the head.
- Recursive Step:
- Swap the first two nodes.
- Continue swapping for the rest of the list using recursion.
Code:
Complexity Analysis
- Time Complexity: O(n), since each pair of nodes is processed once and in constant time.
- Space Complexity: O(n) due to recursion stack space used for each node.
Iterative Approach
The iterative approach involves using a dummy node to facilitate the swapping process as we walk through the list:
- Setup a Dummy Node: This helps manage edge cases and makes node swapping easier.
- Traversal and Swapping:
- Swap nodes by adjusting pointers.
- Use a loop to continue swapping until the end of the list is reached.
Code:
Complexity Analysis
- Time Complexity: O(N) since we traverse each node of the list exactly once.
- Space Complexity: O(1) as no additional space is used other than a few pointers.