学习记录，主要参考：代码随想录
24. 两两交换链表中的节点
题目链接:https://leetcode.cn/problems/swap-nodes-in-pairs/description/
文章讲解:https://programmercarl.com/0024.%E4%B8%A4%E4%B8%A4%E4%BA%A4%E6%8D%A2%E9%93%BE%E8%A1%A8%E4%B8%AD%E7%9A%84%E8%8A%82%E7%82%B9.html
视频讲解:https://www.bilibili.com/video/BV1YT411g7br/?spm_id_from=333.788&vd_source=e70917aa6392827d1ccc8d85e19e8375
实现情况：
切记本题不能修改节点内部的值
思路 使用虚拟头节点，然后如果需要置换位置的处理情况一样
1、记录后面节点
2、交换节点
3、移动指针
4、循环前面步骤
5、结束条件是后面没有需要操作的两个节点了
/**
* 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) {
if (head == nullptr || head->next == nullptr) { // 只有一个节点或者空链表
return head;
}
ListNode* dummy_head = new ListNode(0);
dummy_head->next = head;
ListNode* cur = dummy_head;
while (cur->next && cur->next->next != nullptr) {//确保后面还有两个节点可以进行交换
ListNode* tmp = cur->next->next->next;//记录当前循环不需要处理的节点信息
ListNode* tmp1 = cur->next;//记录需要删除节点
cur->next = cur->next->next;//相当于删除中间的节点
cur->next->next = tmp1;//将删除的节点补到后面
cur->next->next->next = tmp;//恢复全部链表
cur = cur->next->next;//将cur指针移动到下一个“虚节点”位置，方便后续的处理
}
head = dummy_head->next;
delete dummy_head;
return head;
}
};
9.删除链表的倒数第N个节点
题目链接:https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/
文章讲解:https://programmercarl.com/0019.%E5%88%A0%E9%99%A4%E9%93%BE%E8%A1%A8%E7%9A%84%E5%80%92%E6%95%B0%E7%AC%ACN%E4%B8%AA%E8%8A%82%E7%82%B9.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
视频讲解:https://www.bilibili.com/video/BV1vW4y1U7Gf/?spm_id_from=333.788&vd_source=e70917aa6392827d1ccc8d85e19e8375
实现情况：
这里不需要判断n值的有效性？
实现思路，双指针
1、快指针先移动n 个位置，fast指针不能为空
2、fast指针需要提前走一步
3、两个指针同时移动，fast指针不能为空
3、删除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);
dummyHead->next = head;
ListNode* slow = dummyHead;
ListNode* fast = dummyHead;
while (n--&& fast != NULL) {//确保fast指针有效
fast = fast->next;
} fast = fast->next;//fast需要提前走一步
while (fast != nullptr) {
fast = fast->next;
slow = slow->next;
}
ListNode* tmp = slow->next;
slow->next =slow->next->next;
delete tmp;
return dummyHead->next;
}
};
面试题 02.07. 链表相交
题目链接:https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/
文章讲解:https://programmercarl.com/%E9%9D%A2%E8%AF%95%E9%A2%9802.07.%E9%93%BE%E8%A1%A8%E7%9B%B8%E4%BA%A4.html
实现情况：
实现思路
1 计算两个链表的长度
2 确保B是长的链表
3 计算长度差值
4 比较A和B是否有相同的元素 有返回
if (curA == curB):
// if (curA->val == curB->val) {
这是一个指针比较。它检查curA和curB是否指向内存中的同一个位置，即它们是否引用同一个ListNode对象。这种比较通常用于检查两个链表是否在某个节点上相遇（例如，在检测两个链表是否相交时）。
如果curA和curB指向同一个节点，那么curA == curB的结果为true；否则为false。
指针比较不关心节点中存储的值，只关心指针本身。
// if (curA->val == curB->val)（注释掉的代码）:
这是一个值比较。它检查curA和curB所指向的节点的值是否相等。这里假设curA和curB都不是nullptr，因为解引用nullptr会导致运行时错误。
如果curA和curB所指向的节点的值相等，那么curA->val == curB->val的结果为true；否则为false。
值比较关注节点中存储的具体数据，而不是节点本身在内存中的位置。
if (lenB < lenA) {
swap(lenA, lenB);
swap(curA, curB);
}
这段代码的目的是在处理两个链表（假设为链表A和链表B，分别由curA和curB指向它们的头节点）时，确保链表A的长度不小于链表B的长度，并且curA指向较长的链表，curB指向较短的链表。这是通过比较两个链表的长度（lenA和lenB）来实现的，并在必要时交换它们。
/**
* 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* curA = headA;
ListNode* curB = headB;
// 1 计算两个链表的长度
int lenA = 0;
while (curA != NULL) {
curA = curA->next;
lenA++;
}
int lenB = 0;
while (curB != NULL) {
curB = curB->next;
lenB++;
}
// 2 确保B是长的链表
if (lenB < lenA) {
swap(lenA, lenB);
// swap(curA, curB);
swap(headA, headB);
}
// 3 计算长度差值
int gap = lenB - lenA;
curA = headA;
curB = headB;
while (gap--) {
curB = curB->next;
}
// 4 比较A和B是否有相同的元素 有返回
while (curB != NULL) {
// if (curA->val == curB->val) {
if (curA == curB) {
return curB;
}
curB = curB->next;
curA = curA->next;
}
return NULL;
}
};
142.环形链表II
题目链接:https://leetcode.cn/problems/linked-list-cycle-ii/description/
文章讲解:https://programmercarl.com/0142.%E7%8E%AF%E5%BD%A2%E9%93%BE%E8%A1%A8II.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
视频讲解:https://www.bilibili.com/video/BV1if4y1d7ob/?spm_id_from=333.788&vd_source=e70917aa6392827d1ccc8d85e19e8375
实现思路：
一开始想到了双指针，但是怎么计算环的入口没有想清楚！
/**
* 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;
ListNode* slow = head;
while (fast != NULL && fast->next != NULL) {
fast = fast->next;
fast = fast->next;
slow = slow->next;
if (fast == slow) {//快慢指针相遇了
ListNode* index1 = slow;//现在这个节点一定在环内
ListNode* index2 = head;
while (index1 != index2) {//他们在入口处相遇了！！！
index1 = index1->next;
index2 = index2->next;
}
return index2;
}
}
return NULL;
}
};
总结
链表的种类主要为：单链表，双链表，循环链表
链表的存储方式：链表的节点在内存中是分散存储的，通过指针连在一起。
链表的基本操作包括建立链表、插入节点、删除节点、查找节点等。这些操作通常通过遍历链表并修改节点的指针域来实现。
经典题目：
203.移除链表元素：学会使用虚拟头结点
707.设计链表：学会链表的基本操作、获取第n个元素、头部插入、尾部插入、第n个节点前插入、删除第n个节点；统一使用虚拟头结点，操作便捷
19.删除链表的倒数第N个节点：虚拟头节点+双指针+窗口概念解决
206.反转链表：使用双指针解决
24. 两两交换链表中的节点：添加虚拟头节点后续统一操作，注意判断条件，要满足虚拟头结点后面有两个节点可以进行交换
面试题 02.07. 链表相交 ：注意节点数值相等不是节点等价！！！
142.环形链表II：需要好好思考一下
![苍穹外卖跟练项目前端localhost打不开页面启动nginx报错[alert] could not open error log file问题解决](https://i-blog.csdnimg.cn/direct/a5e427f8daca4ab0975d793e9a6a388f.png)
