算法训练营第四天：链表相关重点精讲

算法训练营第四天|24. 两两交换链表中的节点 、19.删除链表的倒数第N个节点、面试题 02.07. 链表相交 、142.环形链表II

• 昨日回顾
• 24.[两两交换链表中的节点](https://leetcode.cn/problems/swap-nodes-in-pairs/)
• • 卡哥文字以及视频讲解链接
  • • 重点
    • 两两交换链表中的节点c++实现
    • 卡哥PS:这里还是说一下，大家不必太在意力扣上执行用时，打败多少多少用户，这个统计不准确的。
• 19.[删除链表的倒数第N个节点](https://leetcode.cn/problems/remove-nth-node-from-end-of-list/)
• • 卡哥文字以及视频讲解链接
  • • 重点
    • 删除链表的倒数第N个节点c++实现（先检查越界，再完成快慢指针操作）
    • 删除链表的倒数第N个节点c++实现（直接在双指针中检查越界）
• [面试题 02.07. 链表相交](https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/)
• • 卡哥文字以及视频讲解链接
  • • 重点
    • 链表相交c++实现
• 142.[环形链表II](https://leetcode.cn/problems/linked-list-cycle-ii/)
• • 卡哥文字以及视频讲解链接
  • • 重点
    • 环形链表IIc++实现
• 坚持就是胜利

昨日回顾

• 链表定义，要清晰且熟练。
• 链表操作节点时，拥有节点地址（也就是指针域）是第一要务。 使用头节点已知地址搭配前一节点获取后一节点的方法就是在原链表上操作的方法。 定义一个新的头节点指向原链表头节点，将所有节点统一处理就是新建头节点的方法。 两种方法各有优势，头节点思路更为统一，步骤也不复杂，更推荐新建头节点这种方法吧！
• 递归，有其他方法的时候不用死磕。要死磕我也暂时没什么好办法，慢慢总结吧。

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

卡哥文字以及视频讲解链接

重点

• 链表节点两两交换，一定要清楚每一次的循环起始位置在哪！！！
• 1->2->3->4 要变成 2->1->4->3，手动先画一下过程。

两两交换链表中的节点c++实现

cpp

class Solution {
public:
ListNode* swapPairs(ListNode* head) {
ListNode dummy(0);
ListNode* cur = &dummy;
//还是新建头节点，便于统一操作
cur -> next = head;
while(cur -> next != nullptr && cur -> next -> next != nullptr){
//while循环条件还是最后总结
//为什么函数体里没有用到cur -> next -> next -> next，却要求cur -> next -> next != nullptr？
//因为别看表面没有用到，cur -> next = cur -> next -> next;这一步已经改变了指向，之后的cur -> next -> next = temp1;其实是进入while函数体的cur -> next -> next -> next。思考思考。
ListNode* temp1 = cur -> next;
cur -> next = cur -> next -> next;
ListNode* temp2 = cur -> next -> next;
cur -> next -> next = temp1;
temp1 -> next = temp2;
cur = temp1;//cur的位置要清楚，循环的起点要明确。
//上面的步骤没有具体的写法，但是就是有一点，不能丢失哪怕一个节点的地址。
//有了地址，链表节点怎么都能操作。
}
return dummy.next;
}
};

卡哥PS:这里还是说一下，大家不必太在意力扣上执行用时，打败多少多少用户，这个统计不准确的。

先完成再完美，毕竟是刚开始嘛。最后全部学完，想精进，回过头来带复习，带提升，一网打尽。

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

卡哥文字以及视频讲解链接

重点

• 双指针，他又来了。 快指针先走，快慢指针保持固定距离，再同步移动，找到目标位置。
• 增删节点，最好是用前一节点来操作。

删除链表的倒数第N个节点c++实现（先检查越界，再完成快慢指针操作）

cpp

class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode dummy(0);
ListNode* cur = &dummy;
cur -> next = head;
int count = 0;
while(cur -> next != nullptr){
cur = cur -> next;
count++;
}
if(n <= 0 || n > count) return head;
//以上代码是检查n的合法性，防止越界，也防止误删
ListNode* slow = &dummy;
ListNode* fast = slow;
n++;
//加一是因为要想删除一个节点，需要使用前一个结点来执行获得该节点以及跳过该节点链接该节点之后节点的操作
while(n—){
fast = fast -> next;
}//这个while循环确定快慢指针之间的固定步长
while(fast != nullptr){
fast = fast -> next;
slow = slow -> next;
}//同时移动，保持差距，知道快指针走到空
ListNode* temp = slow -> next;
slow -> next = slow -> next -> next;
delete temp;
temp = nullptr;
return dummy.next;
}
};

删除链表的倒数第N个节点c++实现（直接在双指针中检查越界）

class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if (!head || n <= 0) return head; //空指针不要浪费开销，先行处理
ListNode dummy(0);
ListNode* slow = &dummy;
ListNode* fast = slow;
slow -> next = head;
n++;
//加一是因为要想删除一个节点，需要使用前一个结点来执行获得该节点以及跳过该节点链接该节点之后节点的操作
while(n—){
//正常范围内遍历结束，而不是因为 if 跳出，此时 n = -1。
fast = fast -> next;
if(fast == nullptr) break;//指向nullptr，不再参与循环，直接跳出，避免越界
//若跳出，则没有最后一次循环条件的判断，循环结束是n = 0，而不是-1。
}
if(n > 0){
//为什么是n > 0?
//因为有在上面while循环结束的时候，有三种情况
//1. n == -1,fast != nullptr正常情况，n+1 次循环后没有越界
//2. n == 0,fast == nullptr正常情况,n+1 次循环后正好fast指针指向nullptr
//3. n != 0,fast == nullptr循环次数还没有结束 n > 0，是因为要越界提前跳出，说明范围超出，不执行删除
//1 是正常循环结束，而2 ，3是因为fast指向nullptr先行跳出
std::cout << "out of the range" << std::endl;
return head;
}
//以上是检查越界，下面是正常删除
while(fast != nullptr){
slow = slow -> next;
fast = fast -> next;
}
ListNode* temp = slow -> next;
slow -> next = slow -> next -> next;
delete temp;
temp = nullptr;
return dummy.next;
}
};

• 看了卡哥题解以及力扣题解，没有讨论越界情况。大家酌情自己练习。
• 检查过是对的，大家放心使用。

面试题 02.07. 链表相交

卡哥文字以及视频讲解链接

重点

• 唯一重点，为什么要从后对齐长度，再依次对比？
• 因为指针指向是唯一确定的，不存在两条链表先相交后又分开的情况，不管从哪一个节点都只能指向唯一结果

链表相交c++实现

cpp

class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
//先统计两条链表长度，再从后对齐，开始比较
int countA = 0;
int countB = 0;
ListNode* curA = headA;
ListNode* curB = headB;
//这里为什么又不用头节点了？
//方法使用要因地制宜，这里只是遍历查询，不涉及链表的增删，不需要前一节点。
while(curA){
curA = curA -> next;
countA++;
}
while(curB){
curB = curB -> next;
countB++;
}
if(countA > countB){
swap(countA, countB);
swap(headA, headB);
//这两个swap只是交换数据的字面内容，没有一点点别的作用
//只是为了统一处理逻辑
}
curA = headA;
curB = headB;
int count = countB – countA;
while(count—){
curB = curB -> next;
}
while(curA){
if(curA == curB){
return curA;
}
curA = curA -> next;
curB = curB -> next;
}
return nullptr;
}
};

142.环形链表II

卡哥文字以及视频讲解链接

重点

• 环形链表的代码写出来不长，也没有特别的讨论，注意，更重要的是这个数学现象的理解。
• 双指针，已经是基操啦~~~~。
• 第一次循环，慢指针一次一步，快指针一次两步，有情人终成眷属。如果是个圈，两个指针总会相遇。（很好理解）
• 第二次行动，一个指针从头开始，一个指针从相遇点开始，同步一次一步移动。相遇了，就是起点。（为什么！！！）
• 从头开始捋，快慢指针按自己的节奏开始运动到循环了n次再次相遇（如果有环的话，没环直接退出）。
• 为什么能再次相遇？能相遇的原因是因为有环，快指针走过的2n – 慢指针走过的n = m个完整的环（想一下，这一步很容易就理解了。这一步只是说明相差的都是环形节点个数的整数倍）。
• 我们将这个环形链表分成三部分。第一，未进入环形的x长度；第二，从链表环形起点到相遇点的y长度；以及第三，从相遇点同方向移动再次到达链表环形起点的z长度。
• 慢指针：x + ?( z + y) + y = n；就是x长度加上追逐的 ？圈，再加最后没达到满圈的z。
• 快指针：x + (? + m)( z + y) + y = 2n；就是快指针比慢指针多走的m圈加上慢指针走过的长度。（？代表慢指针在环内走过的整圈数）
• 这其实主要是个数学题
• 所以最后 (x + ?( z + y) + y) * 2 = x + (? + m)( z + y) + y；最后两边约一下就是 x + y = (m – ?)( z + y ) —–>x = (m – ? -1)(z + y) + z；还记得x代表什么吗？x就是从链表开头到环形开始的位置。(m – ? -1)这个数字不管有多复杂，他只是代表整圈的移动。这个系数的出现只是说明相遇点出发的指针在一圈一圈地回到相遇点，而从链表头节点出发的指针是在走过 x – z = (m – ? -1)(z + y) 这一段长度。最后两个指针相距链表环形起始点都是z的长度，这时一起移动，相遇的点就是环形的入口位置。

环形链表IIc++实现

cpp

class Solution {
public:
ListNode *detectCycle(ListNode *head) {
//代码实现没什么特别，思路理通就很好实现
ListNode* slow = head;
ListNode* fast = head;
while(fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) {
ListNode* index1 = fast;
ListNode* index2 = head;
while (index1 != index2) {
index1 = index1->next;
index2 = index2->next;
}
return index2;
}
}
return NULL;
}
};

坚持就是胜利

• 第一天，搞定！
• 第二天，搞定！
• 第三天，搞定！
• 第四天，搞定！

author