Description
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 itself may be changed.
Examples
Given 1->2->3->4, you should return the list as 2->1->4->3.
Answer
The main idea of this problem is using two pointers with different speed to find if two pointers will meet. If the given linked list has a cycle in it, then return true . If one of the two pointers reach the edge(NULL) then return false.
Recursive Solution
First decide the input is NULL or it does not have the next node. If yes, then return the input. Use one extra node cur to be the next node of the head and do recursion of cur ‘s next node and set the result as the next node of head’s next. Then point the next of cur to head to do the reverse.
Iterative Solution
Since the reverse is done separately, each time when do the reverse we need to set the new start pre and new cur instead of do the procedure constantly. So we need to record the begin node of the reversed list. Set the node as new_head which new_head->next = head and also initialize iterative node pre as new_head and cur as head.
Time Complexity
The complexity of each method is both O(n) with n as the length of the given linked list.
Code
C++
class Solution {
public: // Iterative
ListNode* swapPairs(ListNode* head) {
if(!head || !head->next) return head;
ListNode* new_head = new ListNode(0);
new_head->next = head;
ListNode* pre = new_head;
ListNode* cur = head;
while(pre->next && cur->next)
{
pre->next = cur->next;
cur->next = cur->next->next;
pre->next->next = cur;
pre = cur;
cur = cur->next;
}
return new_head->next;
}
};
class Solution {
public: // Recursive
ListNode* swapPairs(ListNode* head) {
if(!head || !head->next) return head;
ListNode* cur = head->next;
head->next = swapPairs(cur->next);
cur->next = head;
return cur;
}
};
