Swap Nodes in Pairs
Given a linked list, swap every two adjacent nodes and return its head. You may not modify the values in the list's nodes, only nodes themselves may be changed.
Constraints:
- The number of nodes in the list is in the range [0, 100].
- 0 <= Node.val <= 100
Examples:
Input: [1,2,3,4]
Output: [2,1,4,3]
Explanation: After swapping, the list becomes 2 -> 1 -> 4 -> 3
Solutions
Iterative Approach
Time: O(n)Space: O(1)
We use a dummy node to simplify the code. We initialize three pointers: prev, first, and second. We iterate through the list, swapping every two adjacent nodes.
class Solution {
public: ListNode* swapPairs(ListNode* head) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* prev = dummy;
while (prev->next && prev->next->next) {
ListNode* first = prev->next;
ListNode* second = prev->next->next;
first->next = second->next;
second->next = first;
prev->next = second;
prev = first;
}
return dummy->next;
}
}Follow-up:
What if the linked list has an odd number of nodes?
