leetcode刷题03--链表求环--T141,142

题目:

image.png

T141和T142的区别在于:前者不用返回环起始节点,后者需要

思路1:
用set求解
如图:

image.png

思路很容易理解

直接上代码了

/**
 * 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) {
        //创建set集合
        std::set<ListNode*> node_list;
        //将链表中的集合一个一个放入set中
        while(head){
            //先进行查找
            if(node_list.find(head) != node_list.end()){
                return head;
            }
            node_list.insert(head);
            head = head->next;
        }
        return NULL;
    }
};

思路二:
思路一因为用了set集合,算比较赖皮的做法了,而且时间复杂度较高,下面介绍的思路二时间复杂度会少一些
这里运用了快慢指针的概念:

给出解释:

相当于两个人跑步,一个人快,一个人慢,如果是环形跑道,那么快的那个人
肯定可以追上慢的那个人
这种快慢指针也是如此,一个指针步长为2一个为1,如果两者相遇,则链表必定有环

如图:

image.png

当然,还有一个问题,如何确定环的起点?
这里运用了几何关系,具体解释可以看图
大致意思是:从head起点到环起点的距离和两个快慢指针相遇点到环起点的距离相等.

image.png

好了,思路基本上没有问题了,上代码:

/**
 * 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) {
        //定义快慢指针,都从head开始
        ListNode *slow = head;
        ListNode *fast = head;
        //遍历
        while(fast){
            //slow前进一步
            //fast前进两步
            slow = slow->next;
            //不能直接往下两步,先一步,然后判空后再一步
            fast = fast->next;
            if(!fast){
                //为空直接返回
                return NULL;
            }
            fast = fast->next;
            
            //对比,要相等且不为空
            if(fast == slow){
                //存在环!
                break;  
            }   
        }
        //存在环才会进入此判断内
        if(fast == slow){
            //让head和fast各一步一步向下指,相遇点就是环的起始点
            while(head != fast){
                head = head->next;
                fast = fast->next;
            }
            return head;
        }
        return NULL;
        
    }
};

总结:
今天的代码都是自己看了思路之后,直接想的,我想以后也要这样,不能依赖别人的代码,一定要自己亲自实现,否则那些思想和提高始终不会是自己的.
大概刷题流程:
看ppt题目介绍->先自己想如果有思路就尝试
如果没有思路就看ppt的思路,然后自己尝试实现代码,尽量实现,尝试提交
最后进行对比和查看思路差异

加油,天道酬勤,功不唐捐!

最后编辑于：2019.05.10 16:04:49