Problem:
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.
Solution:
//recursive solution
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if (head == NULL || head->next == NULL) return head;
ListNode* next = head->next;
head->next = swapPairs(head->next->next); //important
next->next = head;
head = next;
return head;
}
};
// copy
// iterative solution with dummy node
ListNode *swapPairs(ListNode *head) {
ListNode *dummy = new ListNode(0), *node;
node = dummy;
dummy->next = head;
while (head && head->next) {
ListNode *nxt = head->next;
head->next = nxt->next;
nxt->next = head;
node->next = nxt;
node = head;
head = node->next;
}
return dummy->next;
}
Memo:
Study dummy node.
Recursion need to give some implementation only once, otherwise it will be redundant.
//first version of my recursion code
//works but redundant
ListNode* swapPairs(ListNode* head) {
if (head == NULL || head->next == NULL) return head;
if (head->next->next == NULL) //this part is unnecessary,think why
{
ListNode* next = head->next;
next->next = head;
head->next = NULL;
head = next;
}
else
{
ListNode* next = head->next;
head->next = swapPairs(head->next->next); //important
next->next = head;
head = next;
}
return head;
}
