题目要求: 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。
为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。
说明:不允许修改给定的链表。
进阶:你是否可以不用额外空间解决此题?
一般有两种解题思路,一是利用set来存储链表节点的地址,看哪个重复了,哪个就是入环的第一个节点;二是利用快慢指针,一个快指针,一个慢指针,同时遍历链表看是否存在环,然后再进一步寻找入环的第一个节点。
这里我们不去考虑算法,我们考虑程序自身的特点,我们都知道,
1. 一般内存都在在堆上申请的,而堆的地址空间是从低到高的; 2. 一般我们给链表申请内存空间的时候,一般都是逐个申请并链接,这样链表里的节点的地址也是从低到高的;幸运的是LeetCode的开发者的也是这样想的,(●'◡'●),这一点是关键。
那么,如果链表里面存在环,那么入环第一个节点的地址一定小于或等于最后一个节点的地址。我们只需要返回第一个地址小于或等于前一个节点的节点,即可。
1. 等于的情况是链表只有一个节点,并和自己组成了一个环。 2. 如果链表中不存在环,则最后一个节点的下一个节点是nullptr,也就是0,而0小于等于任何地址。
这样我们的算法只需要遍历一遍链表,并且不使用额外的内存空间,算法复杂度o(n),空间复杂度o(1)。
那么,成了!详细代码如下。
- class Solution {
- public:
- ListNode *detectCycle(ListNode *head) {
- while(head) {
- if(!less<ListNode *>()(head, head->next)) {
- return head->next;
- }
- head = head->next;
- }
- return nullptr;
- }
- };
复制代码注1:C++中并不能直接使用操作符<、>对指针(地址)进行比较,所以采用less模板。
今天这道题是每日一题,我的邪道答案点赞数终于超过了正经答案了,哈哈哈哈哈。 目前191赞 已经超过了快慢指针的186赞
|