链表 合集
一. 206. 反转链表🔗
题目要求：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
四步走三节点：cur走到fore，fore往下走，cur指向pre，pre向前一步走到cur
cur = fore; —— 定位：把“未来”即将处理的节点，变成“当前”节点。
fore = fore->next; —— 探路：“未来”指针继续向前一步，防止断链。
cur->next = pre; —— 反转：“当前”节点掉头，指向“先前”的节点。
pre = cur; —— 跟进：“先前”指针往前挪，接替现在的“当前”位置。
1. 正常做法
classSolution{public:ListNode*reverseList(ListNode*head){if(head==nullptr||head->next==nullptr)returnhead;ListNode*cur=nullptr;ListNode*fore=head;ListNode*pre=nullptr;while(fore){cur=fore;fore=fore->next;cur->next=pre;pre=cur;}returncur;}};二. 160. 相交链表🔗
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
2. 正常做法
a+c+b=b+c+a，c是公共长度，a和b是不相交的长度。遍历完旧的链表，就跑到另一个链表。
为什么要让
pa走完自己的路去走pb的路？
因为两个链表长度可能不一样（比如 A 长 B 短）。如果大家各走各的，永远碰不到一起。但是，如果我走完我的路，再去走你的路；你走完你的路，再来走我的路，我们俩走过的总距离就一定相等了。既然总距离相等，速度又一样（每次走一步），只要我们有公共节点，就绝对会在公共节点准时相遇。
- 当链表完全不相交时，
pa遍历完 A 去走 B，pb遍历完 B 去走 A。- 当他们把彼此的路都走完时，都走了m + n m + nm+n步。
- 此时，
pa刚好走到 B 的尽头（变成nullptr），pb也刚好走到 A 的尽头（变成nullptr）。while(pa != pb)判定nullptr != nullptr为假，完美跳出循环，最终返回nullptr。
classSolution{public:ListNode*getIntersectionNode(ListNode*headA,ListNode*headB){if(headA==nullptr||headB==nullptr)returnnullptr;ListNode*pa=headA;ListNode*pb=headB;while(pa!=pb){pa=pa==nullptr?headB:pa->next;pb=pb==nullptr?headA:pb->next;}returnpa;}};三. 234. 回文链表🔗
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
3.1 笨做法–空间复杂度
classSolution{public:boolisPalindrome(ListNode*head){vector<int>ret1;ListNode*temp=head;while(temp){ret1.push_back(temp->val);temp=temp->next;}for(inti=0;i<ret1.size();++i){if(ret1[i]!=ret1[ret1.size()-1-i])returnfalse;}returntrue;}};3.2 O(1) 空间复杂度
classSolution{public:ListNode*reverseList(ListNode*head){if(head==nullptr||head->next==nullptr)returnhead;ListNode*prev=nullptr;ListNode*cur=nullptr;ListNode*fore=head;while(fore!=nullptr){cur=fore;fore=fore->next;cur->next=prev;prev=cur;}returnprev;}boolisPalindrome(ListNode*head){if(head==nullptr||head->next==nullptr)returntrue;// 1. 经典快慢指针找中点ListNode*slow=head;ListNode*fast=head;while(fast->next!=nullptr&&fast->next->next!=nullptr){slow=slow->next;fast=fast->next->next;}// 跑完后，slow 刚好停在中点（如果是偶数，停在靠左的中点）// 2. 剪断链表，并套用你的“反转模板”反转后半段ListNode*pre=reverseList(slow->next);// 跑完后，pre 就是反转后的后半段的新头节点//传入 slow->next 的核心意义就在于：强制让后半段脱离中心点，保证 p2 的节点数一定最少。//有了这个保证，while (p2 != nullptr) 就成了绝对安全的屏障，//它保证了在 p2 耗尽之前，p1 绝对不可能变成 nullptr。// 3. 双指针比对ListNode*p1=head;// 前半段的头ListNode*p2=pre;// 后半段的头 (反转后的)boolresult=true;while(p2!=nullptr){// 只要后半段没走完就继续比if(p1->val!=p2->val){result=false;break;// 发现不同，直接标记为 false}p1=p1->next;p2=p2->next;}reverseList(pre);returnresult;}};1. 偶数情况测试：[1, 2, 2, 1]
- 快慢指针跑完后，
slow停在第 1 个2上。- 如果你传
slow：你把[2, 2, 1]拿去反转了。p2长度变成了 3。而p1前半段有效长度只有 2。p2还没走完，p1就提前变成null了，再取p1->val直接崩溃。- 如果你传
slow->next：你准确地切出了纯正的后半段[2, 1]拿去反转。p2（反转后）是1 -> 2 -> null，长度是2。p1从头开始走，因为我们没有显式斩断链表（Y字型结构），p1实际面对的>路径是1 -> 2 -> 2 -> null，长度是3。- 循环
while(p2 != nullptr)跑 2 次后准时刹车。p1走到第二个2时循环就结束>了，完美避开危险！
2. 奇数情况测试：[1, 2, 3, 2, 1]
- 快慢指针跑完后，
slow刚好停在正中间的3上。- 如果你传
slow->next：你跳过了中间节点3（因为回文链表最中间的节点不需要对比），准确把后半段[2, 1]拿去反转。p2（反转后）依然是1 -> 2 -> null，长度是2。p1从头开始，路径是1 -> 2 -> 3 -> 2 -> null，长度是4。- 循环
while(p2 != nullptr)依然只跑 2 次。比对了最外层的1和次外层的2，p2>变成null，准时刹车！中间的3根本不会被比对，逻辑完美闭环。
四. 141. 环形链表🔗
题目要求：给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
4. 快慢指针
//快慢指针classSolution{public:boolhasCycle(ListNode*head){if(head==nullptr||head->next==nullptr)returnfalse;ListNode*fast=head;ListNode*slow=head;while(fast){if(fast->next!=nullptr)fast=fast->next->next;elsereturnfalse;slow=slow->next;if(fast==slow)returntrue;}returnfalse;}};