LeetCode（环形链表）

张开发
• 2026/4/11 21:38:54 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

LeetCode（环形链表）
题目链接https://leetcode.cn/problems/linked-list-cycle-ii/题目描述给定一个链表的头节点head返回链表开始入环的第一个节点。如果链表无环则返回null。如果链表中有某个节点可以通过连续跟踪next指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数pos来表示链表尾连接到链表中的位置索引从 0 开始。如果pos是-1则在该链表中没有环。注意pos不作为参数进行传递仅仅是为了标识链表的实际情况。不允许修改链表。示例 1输入head [3,2,0,-4], pos 1输出返回索引为 1 的链表节点解释链表中有一个环其尾部连接到第二个节点。示例 2输入head [1,2], pos 0输出返回索引为 0 的链表节点解释链表中有一个环其尾部连接到第一个节点。示例 3输入head [1], pos -1输出返回 null解释链表中没有环。提示链表中节点的数目范围在范围[0, 104]内-105 Node.val 105pos的值为-1或者链表中的一个有效索引思路/** * 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* quickhead; ListNode* slowhead; //判断是否有环 while(quickquick-next){ quickquick-next-next; slowslow-next; //如果有环退出 if(quickslow) break; } //while循环执行完成之后都不相等返回无环 if(quicknullptr||quick-nextnullptr) return nullptr; //定义一个从头出发的节点 ListNode* qhead; //定义一个从相遇点出发的结点 ListNode* pquick; //两个指针以同样的速度走相遇点就是入环点 while(q!p){ qq-next; pp-next; } //返回入环点 return q; } };

更多文章