首页 > 其他 > 详细

[LeetCode] 142. Linked List Cycle II

时间:2018-09-27 00:45:05      阅读:185      评论:0      收藏:0      [点我收藏+]

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

题意:找一个链表中是否含有环,如果没有则返回null,如果有则返回环的起点

我的解法,投机取巧了,我改了val的值,再次扫到我改的那个值就是要的节点

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode n = head;
        if(n == null || n.next == null)return null;
        while(n.next != null) {
            if(n.val == -3276800)return n;
            n.val = -3276800;
            n = n.next;
        }
        return null;
    }
}

二次做这个题,其实是做287的时候,发现他们说是这个题的变种,我特意回来重做了一遍

就是用一个慢指针和一个快指针,快指针是慢指针的两倍,他们相遇的时候(因为有环的话一定会相遇。没有相遇证明没有)

将slow或者fast指针指向头,然后步速都变为1;他们再次相遇的时候就是环的入口;

public class Solution {
   public ListNode detectCycle(ListNode head) {
        ListNode n = head;
        if (n == null || n.next == null) return null;
        ListNode pre = head.next;
        ListNode nxt = head.next.next;
        if (pre == null || nxt == null)
            return null;
       
        while (true) {
            if (pre == nxt) break;
            if (pre.next == null) return null;
            pre = pre.next;
            if (nxt.next == null) return null;
            nxt = nxt.next;
            if (nxt.next == null) return null;
            nxt = nxt.next;
        }
        pre = head;
        while (pre != nxt) {
            pre = pre.next;
            nxt = nxt.next;
        }
        return pre;

    }
}

 

补充:这个算法可能很难去理解,这么证明我就不写了(毕竟本人不擅长画图)

有兴趣的小伙伴可以去证明一下,或者大家直接将结论记住吧

[LeetCode] 142. Linked List Cycle II

原文:https://www.cnblogs.com/Moriarty-cx/p/9710737.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!