美文网首页
leetcode刷题03--链表求环--T141,142

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

作者: KiritoH | 来源:发表于2019-05-10 15:52 被阅读0次

    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的思路,然后自己尝试实现代码,尽量实现,尝试提交
    最后进行对比和查看思路差异

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

    相关文章

      网友评论

          本文标题:leetcode刷题03--链表求环--T141,142

          本文链接:https://www.haomeiwen.com/subject/cxeaoqtx.html