首页 > 其他 > 详细

找出链表环的入口

时间:2020-05-19 22:40:12      阅读:51      评论:0      收藏:0      [点我收藏+]

问题:

  给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。

 

分析:快慢指针+公式推导

  参考:https://www.nowcoder.com/questionTerminal/253d2c59ec3e4bc68da16833f79a38e4?f=discussion(来源:牛客网)

 

code:

  

public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode EntryNodeOfLoop2(ListNode pHead){
        //参考的别人的代码:快慢指针+公式推导
        /*
        推导结果:如果存在循环
        (1)第一次出发:快指针(一次走两步),慢指针一次一步,最终一定会在环的某点相遇
        (2)第二次出发:两个指针分别从头结点和相遇节点出发,最后一定会在环入口节点相遇
         */
        if(pHead==null){
            return null;
       }else{
            ListNode low= pHead;
            ListNode fast = pHead;
           while(fast!=null &&fast.next!=null){
                fast = fast.next.next;
                low = low.next;
                if(fast==low) break;
           }
           //没找到环
           if(fast==null || fast.next==null) return null;

           //找到环,根据结论2寻找环入口
           fast=pHead;
           while(fast!=low){
               fast = fast.next;
               low = low.next;
           }
           return fast;
       }
    }

 

大佬的代码:

  public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }
public ListNode EntryNodeOfLoop(ListNode pHead)
    {
            ListNode fast=pHead;
            ListNode low=pHead;
            while(fast!=null&&fast.next!=null){
                fast=fast.next.next;
                low=low.next;
                if(fast==low)
                    break;
            }
            if(fast==null||fast.next==null)
                return null;
            low=pHead;
            while(fast!=low){
                fast=fast.next;
            low=low.next;
        }
        return low;
    }

 

找出链表环的入口

原文:https://www.cnblogs.com/dream-flying/p/12919979.html

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