Given a linked list, swap every two adjacent nodes and return its head.
For example,
Given 1->2->3->4, you should return the list as 2->1->4->3.
Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.
Note:
- Needs a dummy node to be the head of the list, return dummy.next
- Needs a prev to keep track of the node before the 1st node
- Needs a first node to keep track of the 1st node of the two nodes that needs swapped
- Needs a second node to keep track of the 2nd node of the two nodes that needs swapped
- Needs a remaining node to keep track of all the nodes after the second node
// C++ code
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if (head == NULL) {
return NULL;
}
ListNode dummy = ListNode(0);
ListNode* first = head; // 1st node of two adjacent nodes
ListNode* second = head->next; // 2nd node of two adjacent nodes
ListNode* prev = &dummy;
while(second != NULL) {
ListNode* remaining = second->next;
second->next = first;
prev->next = second;
first->next = remaining;
prev = first;
first = remaining;
if (first == NULL) {
break;
}
second = first->next;
}
dummy.next = (dummy.next == NULL) ? first : dummy.next;
return dummy.next;
}
};