[leetcode] 24 Swap Nodes in Pairs(交換鏈表相鄰結點)

[leetcode] 24 Swap Nodes in Pairs(交換鏈表相鄰結點)

（一）迭代法

在處理這種問題時，我們通常加上一個dummy頭結點指向head，至於思路很清晰了就是隔一個去交換兩個相鄰結點，比如1->2->3->4->NULL，我們先通過指針交換1和2，再交換3和4，詳細的指針操作可以看下面的圖：

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
       ListNode *dummy=new ListNode(0);
	   dummy->next=head;
	   ListNode *prev=dummy,*cur=head;
	   while(cur&&cur->next)
	   {
   	       prev->next=cur->next;
		   cur->next=cur->next->next; //先確定後繼 
		   prev->next->next=cur;
		   
		   prev=cur;
		   cur=cur->next;	
   	   }   
   	   return dummy->next;
    }
};

遞歸一向是以精巧著稱，我們只需處理好最基礎的一部分，剩下的遞歸即可。如果讀者不是很理解的話，可以手動模擬一下。

class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
       if (head == NULL)
            return NULL;
       if (head -> next == NULL)
            return head;
       ListNode *tmp = head -> next;
       head -> next = swapPairs(tmp -> next);
       tmp -> next = head; // 指向下一部分 
       return tmp;
    }
};