代码随想录算法训练营第四天|LeetCode24，19，02.07，142
LeetCode 24 两两交换链表中的节点
题目链接：https://leetcode.cn/problems/swap-nodes-in-pairs/description/
//采用虚拟头节点
/**
* 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 *virtualHead = new ListNode();
virtualHead->next = head;
//保存要进行交换的节点
ListNode *pre = virtualHead;
ListNode *ptr = head;
ListNode *tmp;
while(ptr && ptr->next != NULL){
tmp = ptr->next;
ptr->next = tmp->next;
tmp->next = ptr;
pre->next = tmp;
pre = ptr;
ptr = ptr->next;
}
return virtualHead->next;
}
};
要点：分清pre ，tmp，ptr指针指向的节点
视频讲解链接：https://www.bilibili.com/video/BV1YT411g7br/?spm_id_from=333.788&vd_source=8d6cce160628d93add1e5fa9299f622d
文章讲解链接：https://programmercarl.com/0024.两两交换链表中的节点.html
LeetCode 19 删除链表的倒数第 N 个结点
题目链接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/
//版本一：先计算链表长度，算出删除元素的正数位置，再遍历整个链表
/**
* 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 *virtualHead = new ListNode();
virtualHead->next = head;
//确定该链表的长度
ListNode *ptr = virtualHead;
int size = 0;
while(ptr->next != NULL){
ptr = ptr->next;
size++;
}
//遍历该链表
ListNode *ptr1 = virtualHead;
ListNode *ptr2 = head;
//计算是正数第几个节点
int index = size - n + 1;
//记录要删除的节点
ListNode *tmp;
while(--index){
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
tmp = ptr2;
ptr1->next = ptr2->next;
delete tmp;
return virtualHead->next;
}
};
视频讲解链接：https://www.bilibili.com/video/BV1vW4y1U7Gf/?spm_id_from=333.788&vd_source=8d6cce160628d93add1e5fa9299f622d
文章讲解链接：https://programmercarl.com/0019.删除链表的倒数第N个节点.html
根据视频和文章讲解做出如下总结：
1.设置虚拟头节点，方便处理实际删除的节点。
2.定义fast和slow指针，初始值为虚拟头节点。
3.fast首先走n+1步，是为了让slow指向要删除节点的前一个节点。
4.fast和slow同步走，直到fast走到末尾NULL处。
5.删除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 *virtualHead = new ListNode();
virtualHead->next = head;
//此处不使用遍历链表确认长度的方式，使用快慢双指针
ListNode *slowptr = virtualHead;
ListNode *fastptr = virtualHead;
//让快指针比慢指针快 n+1 步，这样慢指针正好能指向删除结点的前一个位置
n = n + 1;
while(n-- && fastptr != NULL){
fastptr = fastptr->next;
}
//快慢指针同时移动，直到快指针指向NULL值
while(fastptr != NULL){
slowptr = slowptr->next;
fastptr = fastptr->next;
}
//删除节点
ListNode *tmp = slowptr->next;
slowptr->next = tmp->next;
delete tmp;
return virtualHead->next;
}
};
LeetCode 面试题 02.07. 链表相交
题目链接：https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/
//通过将A和B链表对齐的方式，遍历比较,代码基本一次过
/**
* 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) {
//首先求出两个链表的长度
int size1 = 0, size2 = 0;
//确定A链表的长度
ListNode *ptr = headA;
while(ptr != NULL){
ptr = ptr->next;
size1++;
}
//确定B链表的长度
ptr = headB;
while(ptr != NULL){
ptr = ptr->next;
size2++;
}
//将A链表与B链表对齐
ListNode *ptr1 = headA;
ListNode *ptr2 = headB;
//让ptr1成为最长链表的表头
if(size1 < size2){
swap(size1, size2);
swap(ptr1, ptr2);
}
//求A和B的长度差
int len = size1 - size2;
//使ptr1和ptr2对齐
while(len--) ptr1 = ptr1->next;
//遍历A和B链表，依次做比较
while(ptr1 != NULL){
if(ptr1 == ptr2){
return ptr1;
}
ptr1 = ptr1->next;
ptr2 = ptr2->next;
}
return NULL;
}
};
文章讲解链接：https://programmercarl.com/面试题02.07.链表相交.html
LeetCode 142 环形链表 II
题目链接：https://leetcode.cn/problems/linked-list-cycle-ii/description/
//完全失败的代码，竟然使用了双重循环来找环形，快慢指针没想到真是不应该！
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
ListNode *detectCycle(ListNode *head) {
//使用双重循环会超出时间限制
//pos不作为参数传递，说明节点的数据成员不包括pos
//先用双重循环试试
ListNode *ptr1 = head;
ListNode *ptr2 = head->next;
//带环的链表貌似算不出链表长度
for(;ptr1 != NULL; ptr1 = ptr1->next){
for(; ptr2 != NULL; ptr2 = ptr2->next){
if(ptr2 == ptr1){
return ptr1;
}
}
}
return NULL;
}
视频讲解链接：https://www.bilibili.com/video/BV1if4y1d7ob/?spm_id_from=333.788&vd_source=8d6cce160628d93add1e5fa9299f622d
文章讲解链接：https://programmercarl.com/0142.环形链表II.html
本题非常值得记录，里面蕴含的有关数学不等式的思想非常有趣。
根据视频和文章讲解链接做出如下总结：
1.判断链表是否有环，可以使用快慢指针法，分别定义快指针和慢指针，从头节点出发，快指针每次走两步，慢指针每次走一步。这时候可能有疑问，为什么快指针会追上慢指针呢？而不是快指针和慢指针永远错开呢？首先，fast指针一定先进入环中，如果fast指针和slow指针相遇，那一定是在环中相遇。 其次，对于环来说，可以画一个环，让环中的fast指针在任何一个节点追逐slow指针，因为fast是走两步的，slow是走一步的，在环中fast相当于以相对快slow一步的速度来追赶slow。可以假设slow静止不动，fast以一次一步的速度来追赶，所以一定能追得上。
2.如果有环，如何找到环的入口位置？假设头节点到环的入口的节点数为x，环入口到快慢指针相遇的节点的节点数为y，从相遇节点到环入口节点位置的节点数为z。
3.根据上图，可以知道，相遇时slow指针走了x+y的距离，fast指针走了x + n(y + z) + y，n为fast指针在环中转了n圈才遇到slow指针。
$$
fast = 2节点/步; slow = 1节点/步;
$$
$$
2(x + y) = x + n * (y+z)+y;
$$
$$
x+y = n*(y+z);
$$
$$
x=n*(y+z)-y;
$$
$$
x=(n-1)(y+z)+z;n>=1
$$
4.由上面的公式可以看出，当 n = 1时，x = z。这就意味着，从头节点出发一个节点，和相遇节点出发一个节点，这两个指针每次只走一个节点，那么两个节点相遇的节点位置就是环形的入口位置。
5.验证是否有环设置fastptr和slowptr指针；找到环入口设置index1和index2指针。
6.tips补充：在慢指针移动过程中，为什么最后走得距离是 x+y 而不是 x + k*（y+z) + y呢？也就是为什么slow指针在环中只用走不到一圈就会被fast指针追上？首先，slow指针进环中时，fast指针已经进环，此时可以将环铺开成若干条线（因为可以循环无数次）。
$$
当slow走完一圈时，fast一定走在slow的前面，说明fast和slow已经相遇过；
$$
/**
* 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 *slowptr = head;
ListNode *fastptr = head;
//设置两个指针，确定环入口的位置
ListNode *index1, *index2;
//fastptr一次走两个节点，slowptr一次走一个节点
while(fastptr != NULL && fastptr->next != NULL){
fastptr = fastptr->next->next;
slowptr = slowptr->next;
if(fastptr == slowptr){ //说明相遇，有环
//现在确认环的入口
index1 = head;
index2 = fastptr;
while(index1 != index2){
index1 = index1->next;
index2 = index2->next;
}
return index1;
}
}
return NULL;
}
};