首页 > 其他 > 详细

面试题23:链表环中的入口节点

时间:2020-01-21 20:33:29      阅读:31      评论:0      收藏:0      [点我收藏+]

标签:出了   {}   两个   eof   str   自己   

1、题目描述:

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

2、思路:这道题因为题目中说了链表不一定有环,那么我们首先就是要判断这个链表是否有环,判断有环的方法就是定义两个指针,第一个指针一次走一步,第二个指针一次走两步。因为有环的存在,这两个指针一定会相遇,记下此时的相遇的节点,还可以算出环的节点的个数。

  算出了环中节点的个数n了,只需要重新定义两个指针,第一个指针比第二个指针晚走n步,这时候两个指针相遇的节点就是环的入口节点。

3、代码:

public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
        ListNode meetNode = meetNode(pHead);
        if (meetNode == null) {
            return null;
        }
        //计算环的节点数,用相遇节点作为起点,从前往后走,计数即可
        //cicleCount从1开始,因为有只有一个节点的环{}{1},即next指向自己,对应的输出应该为1
        int cicleCount = 1;
        ListNode pNode = meetNode;
        while (pNode.next != meetNode) {
            cicleCount++;
            pNode = pNode.next;
        }
        //定义两个指针,第一个指针原位,第二个指针提前向前走cicleCount步
        ListNode aheadNode = pHead;
        ListNode behindNode = pHead;
        for (int i = 0; i < cicleCount; i++) {
            aheadNode = aheadNode.next;
        }
        //求环入口节点,两个指针一起走,相遇的就是入口节点
        while (aheadNode != behindNode) {
            aheadNode = aheadNode.next;
            behindNode = behindNode.next;
        }
        return behindNode;
    }

    public static ListNode meetNode(ListNode pHead) {
        if (pHead == null) {
            return null;
        }

        ListNode slowNode = pHead.next;
        if (slowNode == null) {
            return null;
        }
        ListNode fastNode = slowNode.next;

        while (slowNode != null && fastNode != null) {
            if (slowNode == fastNode) {
                return slowNode;
            } else {
                slowNode = slowNode.next;
                if (slowNode == null) {
                    break;
                }
                fastNode = fastNode.next;
                if (fastNode != null) {
                    fastNode = fastNode.next;
                }

            }
        }
        return null;
    }
}

面试题23:链表环中的入口节点

标签:出了   {}   两个   eof   str   自己   

原文:https://www.cnblogs.com/guoyu1/p/12222936.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号