[LeetCode] 24. Swap Nodes in Pairs

佚名 4年前 (2020-02-18) 算法 511人围观抢沙发百度已收录

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;
    }
};