一. 206. 反转链表题目要求给你单链表的头节点 head 请你反转链表并返回反转后的链表。四步走三节点cur走到forefore往下走cur指向prepre向前一步走到curcur fore; —— 定位把“未来”即将处理的节点变成“当前”节点。fore fore-next; —— 探路“未来”指针继续向前一步防止断链。cur-next pre; —— 反转“当前”节点掉头指向“先前”的节点。pre cur; —— 跟进“先前”指针往前挪接替现在的“当前”位置。1. 正常做法classSolution{public:ListNode*reverseList(ListNode*head){if(headnullptr||head-nextnullptr)returnhead;ListNode*curnullptr;ListNode*forehead;ListNode*prenullptr;while(fore){curfore;forefore-next;cur-nextpre;precur;}returncur;}};二. 160. 相交链表给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。2. 正常做法acbbcac是公共长度a和b是不相交的长度。遍历完旧的链表就跑到另一个链表。为什么要让pa走完自己的路去走pb的路因为两个链表长度可能不一样比如 A 长 B 短。如果大家各走各的永远碰不到一起。但是如果我走完我的路再去走你的路你走完你的路再来走我的路我们俩走过的总距离就一定相等了。既然总距离相等速度又一样每次走一步只要我们有公共节点就绝对会在公共节点准时相遇。当链表完全不相交时pa遍历完 A 去走 Bpb遍历完 B 去走 A。当他们把彼此的路都走完时都走了m n m nmn步。此时pa刚好走到 B 的尽头变成nullptrpb也刚好走到 A 的尽头变成nullptr。while(pa ! pb)判定nullptr ! nullptr为假完美跳出循环最终返回nullptr。classSolution{public:ListNode*getIntersectionNode(ListNode*headA,ListNode*headB){if(headAnullptr||headBnullptr)returnnullptr;ListNode*paheadA;ListNode*pbheadB;while(pa!pb){papanullptr?headB:pa-next;pbpbnullptr?headA:pb-next;}returnpa;}};三. 234. 回文链表给你一个单链表的头节点 head 请你判断该链表是否为回文链表。如果是返回 true 否则返回 false 。3.1 笨做法–空间复杂度classSolution{public:boolisPalindrome(ListNode*head){vectorintret1;ListNode*temphead;while(temp){ret1.push_back(temp-val);temptemp-next;}for(inti0;iret1.size();i){if(ret1[i]!ret1[ret1.size()-1-i])returnfalse;}returntrue;}};3.2 O(1) 空间复杂度classSolution{public:ListNode*reverseList(ListNode*head){if(headnullptr||head-nextnullptr)returnhead;ListNode*prevnullptr;ListNode*curnullptr;ListNode*forehead;while(fore!nullptr){curfore;forefore-next;cur-nextprev;prevcur;}returnprev;}boolisPalindrome(ListNode*head){if(headnullptr||head-nextnullptr)returntrue;// 1. 经典快慢指针找中点ListNode*slowhead;ListNode*fasthead;while(fast-next!nullptrfast-next-next!nullptr){slowslow-next;fastfast-next-next;}// 跑完后slow 刚好停在中点如果是偶数停在靠左的中点// 2. 剪断链表并套用你的“反转模板”反转后半段ListNode*prereverseList(slow-next);// 跑完后pre 就是反转后的后半段的新头节点//传入 slow-next 的核心意义就在于强制让后半段脱离中心点保证 p2 的节点数一定最少。//有了这个保证while (p2 ! nullptr) 就成了绝对安全的屏障//它保证了在 p2 耗尽之前p1 绝对不可能变成 nullptr。// 3. 双指针比对ListNode*p1head;// 前半段的头ListNode*p2pre;// 后半段的头 (反转后的)boolresulttrue;while(p2!nullptr){// 只要后半段没走完就继续比if(p1-val!p2-val){resultfalse;break;// 发现不同直接标记为 false}p1p1-next;p2p2-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和次外层的2p2变成null准时刹车中间的3根本不会被比对逻辑完美闭环。四. 141. 环形链表题目要求给你一个链表的头节点 head 判断链表中是否有环。如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 则返回 true 。 否则返回 false 。4. 快慢指针//快慢指针classSolution{public:boolhasCycle(ListNode*head){if(headnullptr||head-nextnullptr)returnfalse;ListNode*fasthead;ListNode*slowhead;while(fast){if(fast-next!nullptr)fastfast-next-next;elsereturnfalse;slowslow-next;if(fastslow)returntrue;}returnfalse;}};
链表 合集
一. 206. 反转链表题目要求给你单链表的头节点 head 请你反转链表并返回反转后的链表。四步走三节点cur走到forefore往下走cur指向prepre向前一步走到curcur fore; —— 定位把“未来”即将处理的节点变成“当前”节点。fore fore-next; —— 探路“未来”指针继续向前一步防止断链。cur-next pre; —— 反转“当前”节点掉头指向“先前”的节点。pre cur; —— 跟进“先前”指针往前挪接替现在的“当前”位置。1. 正常做法classSolution{public:ListNode*reverseList(ListNode*head){if(headnullptr||head-nextnullptr)returnhead;ListNode*curnullptr;ListNode*forehead;ListNode*prenullptr;while(fore){curfore;forefore-next;cur-nextpre;precur;}returncur;}};二. 160. 相交链表给你两个单链表的头节点 headA 和 headB 请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点返回 null 。2. 正常做法acbbcac是公共长度a和b是不相交的长度。遍历完旧的链表就跑到另一个链表。为什么要让pa走完自己的路去走pb的路因为两个链表长度可能不一样比如 A 长 B 短。如果大家各走各的永远碰不到一起。但是如果我走完我的路再去走你的路你走完你的路再来走我的路我们俩走过的总距离就一定相等了。既然总距离相等速度又一样每次走一步只要我们有公共节点就绝对会在公共节点准时相遇。当链表完全不相交时pa遍历完 A 去走 Bpb遍历完 B 去走 A。当他们把彼此的路都走完时都走了m n m nmn步。此时pa刚好走到 B 的尽头变成nullptrpb也刚好走到 A 的尽头变成nullptr。while(pa ! pb)判定nullptr ! nullptr为假完美跳出循环最终返回nullptr。classSolution{public:ListNode*getIntersectionNode(ListNode*headA,ListNode*headB){if(headAnullptr||headBnullptr)returnnullptr;ListNode*paheadA;ListNode*pbheadB;while(pa!pb){papanullptr?headB:pa-next;pbpbnullptr?headA:pb-next;}returnpa;}};三. 234. 回文链表给你一个单链表的头节点 head 请你判断该链表是否为回文链表。如果是返回 true 否则返回 false 。3.1 笨做法–空间复杂度classSolution{public:boolisPalindrome(ListNode*head){vectorintret1;ListNode*temphead;while(temp){ret1.push_back(temp-val);temptemp-next;}for(inti0;iret1.size();i){if(ret1[i]!ret1[ret1.size()-1-i])returnfalse;}returntrue;}};3.2 O(1) 空间复杂度classSolution{public:ListNode*reverseList(ListNode*head){if(headnullptr||head-nextnullptr)returnhead;ListNode*prevnullptr;ListNode*curnullptr;ListNode*forehead;while(fore!nullptr){curfore;forefore-next;cur-nextprev;prevcur;}returnprev;}boolisPalindrome(ListNode*head){if(headnullptr||head-nextnullptr)returntrue;// 1. 经典快慢指针找中点ListNode*slowhead;ListNode*fasthead;while(fast-next!nullptrfast-next-next!nullptr){slowslow-next;fastfast-next-next;}// 跑完后slow 刚好停在中点如果是偶数停在靠左的中点// 2. 剪断链表并套用你的“反转模板”反转后半段ListNode*prereverseList(slow-next);// 跑完后pre 就是反转后的后半段的新头节点//传入 slow-next 的核心意义就在于强制让后半段脱离中心点保证 p2 的节点数一定最少。//有了这个保证while (p2 ! nullptr) 就成了绝对安全的屏障//它保证了在 p2 耗尽之前p1 绝对不可能变成 nullptr。// 3. 双指针比对ListNode*p1head;// 前半段的头ListNode*p2pre;// 后半段的头 (反转后的)boolresulttrue;while(p2!nullptr){// 只要后半段没走完就继续比if(p1-val!p2-val){resultfalse;break;// 发现不同直接标记为 false}p1p1-next;p2p2-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和次外层的2p2变成null准时刹车中间的3根本不会被比对逻辑完美闭环。四. 141. 环形链表题目要求给你一个链表的头节点 head 判断链表中是否有环。如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环 则返回 true 。 否则返回 false 。4. 快慢指针//快慢指针classSolution{public:boolhasCycle(ListNode*head){if(headnullptr||head-nextnullptr)returnfalse;ListNode*fasthead;ListNode*slowhead;while(fast){if(fast-next!nullptr)fastfast-next-next;elsereturnfalse;slowslow-next;if(fastslow)returntrue;}returnfalse;}};
