每天一道leetcode142-寻找链表中环的入口

乔戈里

发布于 2019-09-17 15:02:01

5010

发布于 2019-09-17 15:02:01

文章被收录于专栏：Java那些事

题目

每天一道leetcode142-寻找链表中环的入口分类：链表中文链接： https://leetcode-cn.com/problems/linked-list-cycle-ii/ 英文链接 https://leetcode.com/problems/linked-list-cycle-ii/

题目详述

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。说明：不允许修改给定的链表。进阶：你是否可以不用额外空间解决此题？

题目详解

使用额外空间的思路

就是使用一个hashmap，去遍历一遍链表，每遍历一个链表，如果不存在这个节点，那么就插入hashmap，如果存在，说明这个节点已经插入了，那么这个节点就是重复的节点，为啥重复了，就是环的入口节点了。

代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        HashMap<ListNode,Integer> map = new HashMap<>();
        if(head == null || head.next == null)
            return null;
        while(head != null)
        {
            if(map.containsKey(head) == false)
            {
                map.put(head,1);
                head = head.next;
            }else{
                return head;
            }
        }
        return null;
    }
}

代码讲解

15-22行，hashmap判断这个节点如果不存在，那么插入到hashmap里面；
23-24行，hashmap中存在这个节点，那么就返回这个节点，也就是入口节点

不使用额外空间的思路

使用快慢指针，快指针每次走两步，慢指针每次走一步，如果快慢指针相遇说明有环；
有环以后，需要寻找环入口节点，已经找到了一个环的中的节点，利用这个节点，去往下遍历，由于是环，所以这个节点肯定会和自身相遇，相遇以后，记录相遇过程中走的步数，就是环的长度
知道环的长度以后，然后再利用快慢指针的思想，快指针先走环长度，然后快慢指针再一起走，这样因为快指针先走了环的长度，当两者相遇肯定是环的入口节点相遇（为啥呢，因为快慢指针肯定会进入环里面，而由于快指针先走了环的长度，所以也就是一个周期，所以只要进入环，那么这两个指针必然相遇）

代码

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    boolean flag = true;
    public ListNode detectCycle(ListNode head)
    {
        ListNode pHead = head;
        if(pHead == null || pHead.next == null)
            return null;
        ListNode pNode = judgeHasChain(pHead);
        if(pNode != null)
        {
            int lengthChain = 1;
            ListNode pNodeCopy = pNode.next;
            while(pNodeCopy != pNode)
            {
                lengthChain++;
                pNodeCopy = pNodeCopy.next;
            }
            ListNode fast = pHead;
            ListNode slow = pHead;
            int temp = 0;
            while(temp < lengthChain)
            {
                fast = fast.next;
                temp++;
            }
            while(fast != slow)
            {
                fast = fast.next;
                slow = slow.next;
            }
            return fast;
        }
        return null;
    }
    private ListNode judgeHasChain(ListNode pHead)
    {
        ListNode fast = pHead.next;
        ListNode slow = pHead;
        while(fast != slow)
        {
            if(fast != null && fast.next != null)
            {
                fast = fast.next;
            }else{
                flag = false;
                break;
            }
            if(slow != null && slow.next != null)
            {
                slow = slow.next;
            }else{
                flag = false;
                break;
            }
            if(fast == slow)
            {
                return fast;
            }else{
                fast = fast.next;
            }
        }
        if(flag)
            return fast;
        return null;
    }
}