链表的最后两道题

链表相交https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/这里要注意交点不是数值相等而是指针相等思路就是先遍历两遍拿到两条列表的总长度通过计算从同一起点出发如果指针相等了就是交点。简单题吹刘海class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode* curA headA; ListNode* curB headB; int lenA 0, lenB 0; while (curA ! NULL) { // 求链表A的长度 lenA; curA curA-next; } while (curB ! NULL) { // 求链表B的长度 lenB; curB curB-next; } curA headA; curB headB; // 让curA为最长链表的头lenA为其长度 if (lenB lenA) { swap (lenA, lenB); swap (curA, curB); } // 求长度差 int gap lenA - lenB; // 让curA和curB在同一起点上末尾位置对齐 while (gap--) { curA curA-next; } // 遍历curA 和 curB遇到相同则直接返回 while (curA ! NULL) { if (curA curB) { return curA; } curA curA-next; curB curB-next; } return NULL; } };第二道题是求环给定一个链表返回链表开始入环的第一个节点。 如果链表无环则返回 null这道题的思路特别巧妙我自己没想到看了一眼题解后写了出来;第一个卡点是分别定义 fast 和 slow 指针从头结点出发fast指针每次移动两个节点slow指针每次移动一个节点如果 fast 和 slow指针在途中相遇 说明这个链表有环。为什么fast 走两个节点slow走一个节点有环的话一定会在环内相遇呢而不是永远的错开呢首先第一点fast指针一定先进入环中如果fast指针和slow指针相遇的话一定是在环中相遇这是毋庸置疑的。为什么fast指针和slow指针一定会相遇呢因为fast是走两步slow是走一步其实相对于slow来说fast是一个节点一个节点的靠近slow的所以fast一定可以和slow重合于是我写了这样的代码ListNode *fasthead; ListNode *slowhead; if(fast!NULLfast-next-next!NULL){ fastfast-next-next; slowslow-next; while(fastslow){return slow;} } else return NULL; }我真的真的觉得特别对而且简洁但是报错了报错的提示是意思是你的函数承诺了要返回一个值比如返回int或ListNode*但是编译器发现有一条执行路径走到最后没有返回任何东西所以报错了。发现问题是当if条件为真时代码进入分支。如果fast slow不成立绝大多数情况不成立while循环体不执行直接跳过。然后执行完if块函数没有return语句编译器就报错了。于是在while下面加了一行return NULL但还是结果报错了。然后我遇到了第二个卡点快慢指针相遇的地方不一定就是交点怎么解决这个问题我看了题解这里是用数学逻辑推演的我没太看明白但是我记住了结论让现在和fast相遇的slow和head的节点指针同时出发他们相遇的地方就是起点。于是再次修改代码class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode* fast head; ListNode* slow head; while(fast ! NULL fast-next ! NULL) { slow slow-next; fast fast-next-next; // 快慢指针相遇此时从head 和 相遇点同时查找直至相遇 if (slow fast) { ListNode* index1 fast; ListNode* index2 head; while (index1 ! index2) { index1 index1-next; index2 index2-next; } return index2; // 返回环的入口 } } return NULL; } };这两道题都涉及很多数学思维我以前说只要能写出来我肯定能想到思路我错了我错了。