程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> [leetcode] 24 Swap Nodes in Pairs(交換鏈表相鄰結點)

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

編輯:關於C++

(一)迭代法

在處理這種問題時,我們通常加上一個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;
    }
};



 

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved