代码随想录算法训练营第4天 | 24. 两两交换链表中的节点， 19.删除链表的倒数第N个节点，面试题 02.07. 链表相交，142.环形链表II，链表总结

24.两两交换链表中的节点

代码随想录链接

题目

LeetCode-24

给定一个链表，将奇数位与相邻右侧偶数位的节点进行翻转。

自己的想法

使用假表头，遍历时使用一个cur指针指向在需要交换的一对节点的前面一个节点，然后对这一对节点的位置进行交换。

解法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode(0, head); // 一个假表头，并使用构造函数将next指向head节点
        ListNode* cur = dummyHead;                   // cur指针用于遍历链表
        while(cur != NULL && cur -> next != NULL) {  // 如果cur指针为空，或者cur节点后没有节点的话，就跳出循环
            if (cur -> next -> next == NULL) break;  // 如果cur指针指向的节点没有一对节点的话，结束
            ListNode* first = cur -> next;           // 取cur指向的节点后的第一个节点，即奇数位节点
            ListNode* second = first -> next;        // 取要交换的偶数位节点
            ListNode* third = second -> next;        // 取偶数位节点后的节点
            cur -> next = second;                    // 将偶数位节点向前置，置于奇数位节点之前
            second -> next = first;                  // 将奇数位节点置于偶数位节点之后
            first -> next = third;                   // 将原来偶数位节点之后的节点置于奇数位节点之后
            cur = first;                             // 移动cur指针
        }
        return dummyHead -> next;                    // 返回真表头
    }
};

对链表进行遍历，时间复杂度为\(O(n)\)；使用了常数个额外变量，空间复杂度为\(O(1)\)。

19.删除链表中的倒数第N个节点

代码随想录链接

题目

LeetCode-19

给定一个单链表，删除倒数第n个节点。

自己的想法

双指针么，根据给定的n，使快指针先走对应的\((n - 1)\)步, 然后快慢指针再一起移动，当慢指针移动到末尾节点时，慢指针指向的就是要删除的节点。

为什么是\((n - 1)\)步呢，因为这里的想法是使得fast指向最后一个节点时停止，而不是fast为NULL时停止，在这种条件下，fast和slow指针之间的步数差距应该是\((n - 1)\)步，举个例子，如果要删除倒数第2个节点，当fast指向末尾节点时，slow指向的是fast前的一个节点，此时fast和slow之间的步数差距不是2，而是1。

为了能在单链表中正确删除给定位置的节点，还可以让fast在寻找末尾的时候少走一步，这样fast和slow指针一起移动结束之时，slow指针指向的是要被删除的节点之前的节点，便于进行链表操作。

解法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(0, head);                    // 利用构造函数声明一个假表头并让其next指针指向head节点
        ListNode* slow = dummyHead, *fast = dummyHead;                  // 快慢指针
        n--;                                                            // 计算步数差
        while (n-- && fast != NULL) fast = fast -> next;                // 让fast指针先走
        while (fast -> next != NULL && fast -> next -> next != NULL) {  // 当fast指针在倒数第二个节点的时候就停下来，这样slow就在要删除的节点的上一个节点停下来了
            fast = fast -> next;                                        // slow和fast指针同时前进
            slow = slow -> next;
        }
        ListNode* toDel = slow -> next;                                 // 根据上面的思路，此时slow节点的next指针指向的就是要删除的节点，在此标注
        slow -> next = toDel -> next;                                   // 将slow节点的next指针指向要删除的节点的下一个节点，将要删除的节点剥离链表
        delete toDel;                                                   // 释放删除的节点的内存空间
        return dummyHead -> next;                                       // 返回真表头
    }
};

上面的这个代码实现和代码随想录里的C++代码实现有些许的不同，主要区别是在如何处理fast指针的位置，使得slow指针能够停留在要删除的节点的上一个节点处。代码随想录里的做法循环的跳出条件是，fast为空时，slow指针要指向被删除节点的上一个节点，所以fast指针不仅要比slow指针多走n步，甚至还要再多1步；而上面的实现中，fast指针最终停在了末尾节点的上一个节点。作用是一样的。

上面的实现中，时间复杂度为\(O(n)\)，空间复杂度为\(O(1)\)。

链表相交

代码随想录链接

题目

LeetCode-面试题02.07

给定两个链表，要求找到两个链表重合部分的起始节点。王道考研资料数据结构书上的题。

自己的想法

先通过遍历两个链表，获得两个链表分别的长度，再让长链表的遍历指针先走等于长度差的步数，接着让长短链表的遍历指针同时移动，当这两个指针指向同一个节点时，就找到了重合相交部分的起始节点。

解法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode *dummyA = headA, *dummyB = headB;      // 假表头
        ListNode *curA = dummyA, *curB = dummyB;        // 用来计算长度的遍历指针
        int lengthA = 0, lengthB = 0;                   // 长度的变量
        while (curA != NULL && curA -> next != NULL) {  // 查A的长度
            curA = curA -> next;
            lengthA++;
        }
        while (curB != NULL && curB -> next != NULL) {  // 查B的长度
            curB = curB -> next;
            lengthB++;
        }
        ListNode *curLongerList = lengthA >= lengthB ? dummyA : dummyB;             // 根据长度对比，分别确定长链表和锻炼表
        ListNode *curShorterList = lengthA < lengthB ? dummyA : dummyB;
        int steps = lengthA >= lengthB ? (lengthA - lengthB) : (lengthB - lengthA); // 计算步数差
        while (steps--) curLongerList = curLongerList -> next;                      // 长链表先走
        while (curLongerList && curShorterList) {                                   // 长短链表遍历指针同时移动
            if (curLongerList == curShorterList) return curLongerList;              // 当两条链表的遍历指针指向同一个节点时，返回该节点指针
            curLongerList = curLongerList -> next;                                  // 否则，两个指针继续移动
            curShorterList = curShorterList -> next;
        }
        return NULL;                                // 如果一直没有指向同一个节点，证明两链表无相交部分
    }
};

和代码随想录上的C++实现也还是有些许的差别，主要是在确定长短链表那里。

上面的实现遍历了两次链表，时间复杂度为\(O(2 * n) = O(n)\)，使用了常数个变量，空间复杂度为\(O(1)\)。

142.环形链表II

代码随想录链接

题目

LeetCode-142

给定一个链表，返回链表内环形结构开始的节点。若无环，则返回 NULL 。

这道题目不要太熟悉啊，也是王道考研资料的数据结构书上面的题，可能是链表部分练习题的最后一道大题来着。并不耽误我这次一开始自己没做出来。

自己的想法

双指针法，快指针一次走两步，慢指针一次走一步。当快慢指针相遇时，证明有环状结构存在。此时，快指针的步数是慢指针步数的两倍。

示意图，图源代码随想录

设链表入环前的长度为\(x\)，链表环的入口到快慢指针相遇的地方长度为\(y\)，相遇之处从沿快慢指针前进方向距环的入口的长度为\(z\)，可得以下公式：

\begin{equation} 2 * (x + y) = x + n * (x + y) + z \end{equation}

其中，\(n\)为快指针进入环结构之后，完整走完了几次环结构。

根据上面的式子，可得：

\begin{equation} x = (n - 1) * (y + z) + z \end{equation}

\((y + z)\)等于一个环结构的长度，我们假设\(n = 1\)，即快指针完整走完了一次环结构后才与慢指针相遇，可得：

\begin{equation} x = z \end{equation}

此时若新设立一个指针，从链表表头开始，与慢指针同时一步一步前进，则当慢指针走过\(z\)步，新指针走过\(x\)步时，慢指针和新指针将在环结构入口处相遇。

若\(n > 1\)，同样在链表表头设立一个新指针，此时新指针与慢指针的距离为\((x + y)\)。由上面的式子可得：

\begin{equation} x + y = (n - 1) * (y + z) + z + y = n * (y + z) \end{equation}

即此时新指针与慢指针的差距为环形结构的长度的\(n\)倍，在新指针与慢指针同时一步一步前进的条件下，两者最终还是会在环装结构入口处相遇。

解法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast = head, *slow = head;
        while (fast != NULL && fast -> next != NULL) {
            slow = slow -> next;
            fast = fast -> next -> next;
            if (slow == fast) break;
        }
        if (fast == NULL || fast -> next == NULL) return NULL;
        ListNode *prob = head;
        while (prob != slow) {
            prob = prob -> next;
            slow = slow -> next;
        }
        return prob;
    }
};

不知道怎么说这个时间复杂度为好。。。空间复杂度为\(O(1)\)。

链表总结

两天干完链表。感觉链表的内容确实不算那种非常难的知识。最起码给我这个计算机科班的人感觉像是在复习。或这就是为什么卡哥给算法训练营中数组和链表都只安排了两天吧。

链表基础

链表的种类分为：

• 单链表
• 双链表
• 循环链表

链表的存储方式：分散存储，依靠相邻节点之间的指针保持联系。

常见题目

虚拟头节点

虚拟头结点主要使用在单链表遍历过程中需要使用前一个节点才能进行操作时。不使用虚拟头结点也能做，就是要单独处理头结点的情况；而使用虚拟头结点，能够在后续的代码中简化实现。

例题： 代码随想录--LeetCode 203.移除链表元素

链表增删改查

既然是个数据结构嘛，免不了要进行增删（改）查，为什么把改单独括起来呢，因为改的前一步往往是要查。

这种题目考的是链表的一些基础操作，虽然看起来简单，但是非常重要，而且经常会在小地方出错而导致代码不能AC。

例题： 代码随想录--LeetCode 707.设计链表

反转链表

将链表的本末倒置。考察对于链表操作的熟练程度，方法主要有递归法和迭代法。

例题： 代码随想录--LeetCode 206.反转链表

删除倒数第N个节点

双指针法。理清快慢指针之间的关系即可。

例题： 代码随想录--LeetCode 19.删除链表的倒数第N个节点

链表相交

找清楚链表相同的部分，将不同的部分予以对齐。

例题： 代码随想录--LeetCode 面试题 02.07 链表相交

环形链表

这种题目主要是数学公式的推导，实现并非难点。

例题： 代码随想录--LeetCode 142.环形链表II