1. 原題鏈接：https://leetcode.com/problems/swap-nodes-in-pairs/
2. 解題思路
- 利用啞節點將邊界case轉化為一般case，比如head為NULL或者鏈表只有一個節點的情況都可以被轉化
- 正常情況下，依次創建三個指標：prev，p，q，它們之間的關系是：p = prev->next，q = p->next
3. 迭代演算法
- 創建啞節點，創建三個指標：prev，p，q
- 回圈遍歷鏈表，回圈的判斷條件是：p 和 q 都不等于NULL，回圈的步長是每次向前移動兩個節點
- 回圈體執行兩個節點的交換
4. 遞回演算法
- 首先，明確遞回函式的功能：輸入一個鏈表，對該鏈表進行兩兩節點交換的操作，回傳交換之后的鏈表頭節點
- 遞回函式的結束條件：鏈表為NULL或者鏈表只有一個節點
- 遞回函式體的主要內容：涉及到交換，所以需要保存當前兩個節點；根據函式對子鏈表操作之后回傳的結果，對當前兩個節點進行交換（PS：可以理解為后序遍歷，先處理子問題，子問題處理完之后，再對當前狀態進行操作）
5. 實作
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
迭代版本
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode dummy(-1);
dummy.next = head;
ListNode *prev = &dummy;
for(ListNode *p = prev->next; p != NULL && p->next != NULL; p = prev->next){
ListNode *q = p->next;
//swap p and q
p->next = q->next;
q->next = p;
prev->next = q;
prev = p; //注意更新prev指標
}
return dummy.next;
}
};
遞回版本
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
//遞回結束條件
if(head == NULL || head->next == NULL) return head;
ListNode *new_head = head->next; //保存當前兩個節點：head、new_head
ListNode *n = swapPairs(head->next->next); //處理子問題
//處理當前狀態
head->next = n;
new_head->next = head;
return new_head;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/86933.html
標籤：其他
上一篇：樹的子結構
下一篇：二叉樹的鏡像