24. 两两交换链表中的节点
19.删除链表的倒数第N个节点
面试题 02.07. 链表相交
142.环形链表II
一、两两交换链表中的节点
两两交换链表中的节点
注意是两两交换，采用虚拟头结点的方法，因为每次操作单链表都需要找到前一个指针。奇数节点数，最后一个不变；偶数节点数，就是正常的两两交换。
操作节点cur一定要指向要交换的两个节点的前一个节点！
class Solution
{
public:
ListNode *swapPairs(ListNode *head)
{
ListNode *dummy = new ListNode(-1);
dummy->next = head;
ListNode *cur = dummy;
while (cur->next != nullptr && cur->next->next != nullptr)
{
// 记录两个临时节点，方便后续更新操作
ListNode *tmp = cur->next;
ListNode *tmp1 = cur->next->next->next;
cur->next = cur->next->next; // 步骤1
cur->next->next = tmp; // 步骤2
tmp->next = tmp1; // 步骤3
cur = cur->next->next; // cur后移两位
}
return dummy->next;
}
};
整体流程：
ListNode * cur =dummy; // 为啥初始化为dummy？
因为这样才能操作刚刚开始的节点。
while(?) 循环结束条件是啥？
这个要看节点数n的奇偶
3、用&&而不是||
使用 && 而不是 || 是为了确保链表中至少有两个节点才能进行节点交换。
4、不能交换两个cur->next != nullptr && cur->next->next != nullptr 顺序
如果将它们的顺序互换，即 cur->next->next != nullptr && cur->next != nullptr，会导致在访问 cur->next->next 之前访问 cur->next，这可能会产生空指针异常（Null Pointer Exception），因为如果 cur->next 是 nullptr，那么访问 cur->next->next 就会出错。
5、为啥定义临时变量tmp？
因为后续改变指向后，无法再找到该节点的前驱和后继了。
趁着还没有赋值操作步骤1前，把cur->next 保存下来，tmp=cur->next，tmp1=cur->next->next->next;
二、删除链表的倒数第N个节点
19.删除链表的倒数第N个节点
删除的思路都是，直接指向next的next，就相当于删除了。
还是采用虚拟头结点，方便我们删除，不需要特判是不是头删！采用统一的方式进行删除！
class Solution
{
public:
ListNode *swapPairs(ListNode *head)
{
ListNode *dummy = new ListNode(-1);
dummy->next = head;
ListNode *cur = dummy;
while (cur->next != nullptr && cur->next->next != nullptr)
{
// 记录两个临时节点，方便后续更新操作
ListNode *tmp = cur->next;
ListNode *tmp1 = cur->next->next->next;
cur->next = cur->next->next;
cur->next->next = tmp;
tmp->next = tmp1;
cur = cur->next->next;
}
return dummy->next;
}
};
/**********************************分割线*******************************************/
// 双指针删除 倒数第n个节点
class Solution
{
public:
ListNode *removeNthFromEnd(ListNode *head, int n)
{
ListNode *dummy = new ListNode(-1);
dummy->next = head;
ListNode *fast = dummy;
ListNode *slow = dummy;
// 快指针先走n步 ， n--就是n步
while (n-- && fast != nullptr)
{
fast = fast->next;
}
fast = fast->next;// 多走一步
/**************************/
// 快慢指针同时走
while (fast != nullptr)
{
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next; // 删除
return dummy->next;
}
};
如何找到倒数第n个节点？采用快慢指针的方法。
fast首先走n + 1步 ，为什么是n+1呢
因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作）
三、链表相交
面试题 02.07. 链表相交
双指针解法
定义两个指针，a，b，分别从各自的链表头部开始，同时走；a指针走到空了，就把a更新到链表b，b指针也是如此，直到两者相遇。
class Solution
{
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB)
{
ListNode *a = headA, *b = headB;
while (a != b)
{
if (a)
a = a->next;
else
a = headB;
if (b)
b = b->next;
else
b = headA;
}
return a;
}
};
四、环形链表
142.环形链表II
class Solution
{
public:
ListNode *detectCycle(ListNode *head)
{
ListNode *fast = head, *slow = head;
while (fast != nullptr && fast->next != nullptr) // 为啥要判断fast->next?
{
fast = fast->next->next;
slow = slow->next;
// 快慢指针相遇，此时从head 和 meet相遇点，同时新定义节点开始查找直至相遇
if (fast == slow)
{
ListNode *newhead = head;
ListNode *meet = fast;
while (newhead != meet)
{
newhead = newhead->next;
meet = meet->next;
}
return newhead;
}
}
return nullptr;
}
};
1、为何想到用快慢指针来判断有没有环？
假设没有环，那么fast和slow是不可能相遇的；有环的话，那么fast会先进入环中，在里面打转，slow后进入，两者总能够相遇。
2、为何fast一次走两步，slow一次走一步？
进入环后，相当于是fast在以相对速度为1步来追击slow，那么他们必然相遇；如果是其他步数的话，他们两者在环中可能会刚好错过！
3、如何找到入环点？
代码随想录完整证明
他们相遇时：
slow指针走过的路程为: x + y
fast指针走过的路程为：x + y + n (y + z)
速度：slow为1，fast为2
时间是相等的
所以得到等式：
整理得到：x = (n - 1) (y + z) + z，当n=1时，x=z。
结论：这就意味着，从头结点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是环形入口的节点。
4、while(fast!=nullptr && fast ->next!=nullptr) // 为啥要判断fast->next?文章来源：https://www.toymoban.com/news/detail-597388.html
因为fast一次条两步！文章来源地址https://www.toymoban.com/news/detail-597388.html
到了这里，关于代码随想录day4 | 24. 两两交换链表中的节点 19.删除链表的倒数第N个节点 02.07.链表相交 142.环形链表II的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
