两两交换链表中的节点--递归解决

0x01.问题

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

C++结构体：
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 C++函数形式：  ListNode* swapPairs(ListNode* head)

0x02.简要分析

首先清楚两两交换的含义：

• 每两个节点为一对，交换，如果最后还剩一个节点，肯定是不用交换的。
• 例如：123456，交换后应该是214365；12345交换后应该是21435。
• 注意是两个节点完全交换，而不是值进行交换。

我们来考虑一下两个节点交换造成了哪些影响：

• 第一个节点的前一个节点会受到影响，因为前一个节点的下一个改变了。
• 第一个节点的指向会受到影响，现在会指向第二个节点的指向。
• 第二个节点的指向会受到影响，现在会指向第一个节点。

所以我们要交换两个节点，必须满足以下条件：

• 设一个哑节点，解决第一个节点交换和空链表的特殊情况。
• 每次必须记录当前节点的前面一个节点，因为必须改变前面一个节点的指向。

到这里，这个问题基本解决了，但我们还有一种更加巧妙地办法，就是使用递归。

递归的思路是：

• 当链表只剩下一个元素的时候或head为空的时候，返回。
• 每次递归交换一对节点。
• 返回给上一层递归的值是已经交换完成后的子链表。
• 交换的最终思路是一样的。

0x03.解决代码–非递归

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode*dummy=new ListNode(0);
        dummy->next=head;
        ListNode*prenode=dummy;
        while(head&&head->next){
            ListNode*firstnode=head;
            ListNode*secondnode=head->next;
            prenode->next=secondnode;
            firstnode->next=secondnode->next;
            secondnode->next=firstnode;
            prenode=firstnode;
            head=firstnode->next;
        }
        return dummy->next;
    }
};

0x04.解决代码–递归

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(!head||!head->next) return head;
        ListNode*firstnode=head;
        ListNode*secondnode=head->next;
        firstnode->next=swapPairs(secondnode->next);
        secondnode->next=firstnode;
        return secondnode;
    }
};

ATFWUS --Writing By 2020–03–24