本文共 2629 字，大约阅读时间需要 8 分钟。

Given a linked list, swap every two adjacent nodes and return its head.

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example:

Given 1->2->3->4, you should return the list as 2->1->4->3.

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

思路1：设立虚拟头结点并用 p 指向它，node1, node2 指向要交换的两个相邻结点，next 指向 node2 后一个位置的结点，代表后一部分的链表。感觉和 LeetCode 92. Reverse Linked List II 有点像。

然后 node2->next 指向 node1 ，node1->next 指向 next 从而链接后一部分的链表，p->next 指向 node2 和前一部分的链表链接起来：

class Solution {
   public:    ListNode* swapPairs(ListNode* head) {
           ListNode *dummy = new ListNode(0);        dummy->next = head;        ListNode *p = dummy;        while (p->next && p->next->next) {
               ListNode *node1 = p->next;            ListNode *node2 = node1->next;            ListNode *next  = node2->next;            //交换node1和node2            node2->next = node1;            node1->next = next;            p->next = node2;            //为进行下次的交换,p指向靠后的那个结点            p = node1;        }        head = dummy->next;        delete dummy;        return head;    }};

效率如下：

执行用时：4 ms, 在所有 C++ 提交中击败了65.17% 的用户内存消耗：6.6 MB, 在所有 C++ 提交中击败了16.03% 的用户

我们不难发现，其中 next 是不需要的，甚至于我们只需要两个额外的指针 p1, p2 。代码如下，虽然简洁一些，但是可读性不太强：

class Solution {
   public:    ListNode* swapPairs(ListNode* head) {
           ListNode *dummy = new ListNode(0);        dummy->next = head;        ListNode *p1 = dummy, *p2;      //p1位于要翻转的那对结点前一个结点,将p2、p2->next进行交换        while (p1->next && p1->next->next) {
               p2 = p1->next;            p1->next = p2->next;        //p1指向那对结点靠后的结点            p2->next = p1->next->next;  //p2->next指向后一部分的链表            p1->next->next = p2;            p1 = p2;                    //更新p1        }        head = dummy->next;        delete dummy;        return head;    }};

效率如下：

执行用时：4 ms, 在所有 C++ 提交中击败了65.17% 的用户内存消耗：6.4 MB, 在所有 C++ 提交中击败了81.87% 的用户

思路3：不需要虚拟头结点，使用递归优雅地解决这道题，递归的三部曲：

• 找终止条件：本题终止条件很明显，当递归到链表为空或者链表只剩一个元素的时候，不用交换，自然就终止了。
• 找返回值：返回给上一层递归的值，应该是已经交换完成后的子链表。
• 单次的过程：递归重复做一样的事情，所以从宏观上考虑，只用考虑某一步是怎么完成的。假设待交换的俩结点分别为 head 和 next = head->next ，对 head->next->next 进行递归会返回一个处理完成的子链表。于是等价于一个含三个结点的链表交换前两个节点。我们将原本的 head->next 指向下一级返回的子链表，next->next 指向 head ，然后返回 next 作为新的链表头结点即可。

具体代码如下：

class Solution {
   public:    ListNode* swapPairs(ListNode* head) {
           if (head == nullptr || head->next == nullptr) return head; //基准条件        ListNode *next = head->next;        head->next = swapPairs(next->next); //递归处理后一部分的链表        next->next = head;        return next;    }};

效率如下：

执行用时：8 ms, 在所有 C++ 提交中击败了5.92% 的用户内存消耗：6.4 MB, 在所有 C++ 提交中击败了75.47% 的用户

转载地址：https://memcpy0.blog.csdn.net/article/details/108182292 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！