首页 > itarticle > 剑指offer_【55】链表中环的入口结点

剑指offer_【55】链表中环的入口结点

admin 11月 14, 2020 0

1.题目描述

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

2.解题思路

方法1：
利用hashSet不存储重复值的思想
方法2：

链表包含环，像数字6的图形。

(1)设置快慢指针，假设快指针在环内与慢指针相遇，设头节点到入口结点的距离为x,入口结点到相遇点为y,相遇点到入口结点距离为z,则有(x+y)*2 = (x+y+z+y),即z = x，即相遇点到入口结点的距离跟头节点到入口结点的距离相等。

(2)这时再设置fast = pHead,一个指针重头走，另一个指针重相遇节点走，当两个点相等时即为入口节点所在。

3.代码

方法1：

public ListNode (ListNode pHead){
         HashSet<ListNode> hs = new HashSet<ListNode>();
         while(pHead!=null){

             if(!hs.add(pHead))

                 return pHead;

             pHead = pHead.next;

         }

         return null;
}

方法2：

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

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode (ListNode pHead)
    {
        ListNode fast = pHead;
        ListNode slow = pHead;
        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast==slow){
                fast=pHead;
                while (fast!=slow){
                    fast = fast.next;
                    slow = slow.next;
                }
                return fast;
            }

        }
        return null;
    }
}