4.20链表

1.环形链表class Solution { public: bool hasCycle(ListNode *head) { ListNode * currhead; int count0; while(curr!nullptr){ count; currcurr-next; } currhead; while(curr!nullptr){ ListNode* curr2curr; int i0; while(curr2!nullptricount){ if(curr2-nextcurr) return true; curr2curr2-next; i; } currcurr-next; } return false; } };上面是我初次的想法但是完成不了因为环形的count根本统计不了会一直死循环。更好的是用快慢指针class Solution { public: bool hasCycle(ListNode *head) { ListNode * slowhead; ListNode * fasthead; while (slow!nullptrfast!nullptrfast-next!nullptr){ slowslow-next; fastfast-next-next; if(fastslow){ return true; } } return false; } };尤其要注意while (fast fast-next)判断条件fast与fast-next写反会报错因为c有短路你得先确保下一步不踩空才能确保下两步不踩空返回相遇节点版本floyd圈class Solution { public: ListNode *detectCycle(ListNode *head) { ListNode* fasthead; ListNode* slowhead; while(fast!nullptrfast-next!nullptr){ fastfast-next-next; slowslow-next; if(fastslow){ break; } } if(fastnullptr||fast-nextnullptr){ return nullptr; } fasthead; while(fast!slow){ fastfast-next; slowslow-next; } return fast; } }