LeetCode Q24: Swap Nodes in Pairs

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.

Surprising to see the difficulty level of this question is marked as "Medium". But it could be this hard if you really try to solve it in an iterative way. Because you gonna be very careful doing many swaps in one iteration.

However, your life will get easier if you try a recursive solution which basically just takes you no more than 10 lines code such as the one in the below:

	/**
	* 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 head;
	if(head->next==NULL) return head;
	ListNode* p0=head;
	ListNode* p1=head->next;
	ListNode* nextHead=p1->next;
	p1->next=p0;
	p0->next=swapPairs(nextHead);
	return p1;
	}
	};

view raw Q24SwapNodesInPairs.cpp hosted with ❤ by GitHub

Solution 2:

	ListNode* swapPairs(ListNode* head) {
	ListNode* sentinel = new ListNode(0);
	if(head==NULL)
	return sentinel->next;
	sentinel->next = head;
	ListNode* p = sentinel;
	ListNode* p2;
	if(p->next->next!=NULL)
	p2=p->next->next;
	else
	return sentinel->next;
	while(p->next!=NULL&&p2!=NULL){
	ListNode* p1 = p->next;
	p1->next=p2->next;
	p2->next=p1;
	p->next=p2;
	p=p->next->next;
	if(p->next!=NULL&&p->next->next!=NULL)
	p2=p->next->next;
	else
	break;
	}
	return sentinel->next;
	}

view raw Q24-2.cpp hosted with ❤ by GitHub