Leetcode142.环形链表II

1.题目描述

给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

说明:不允许修改给定的链表。

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:tail connects to node index 1
解释:链表中有一个环,其尾部连接到第二个节点。

img

2.解答

首先还是使用HashSet保存标记,这个没什么说的

/**
 * 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) {
        if(head == null)    return null;
        HashSet<ListNode> set = new HashSet<>();
        while(head != null){
            if(set.contains(head))
                return head;
            set.add(head);
            head = head.next;
        }
        return null;
    }
}

这次的要求是不仅验证有没有环,还要找到入环的第一个节点,题解说到了什么弗洛伊德算法,就差一点点啊,我就自己推导出佛洛依德解决这个问题的方法了,但是基本的表达式我已经证明出来了,就是最后碰面的过程,我没有继续想,哎,可惜没如果

image

如上面草图,最终快慢指针会在-4节点相遇,那么这时,根据公式的推导结果,-4到入环节点的距离和head到入环节点的距离是相等的,让head和p1同时向前走,碰面就是入环节点

/**
 * 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) {
        //特殊条件的判定
        if(head == null || head.next == null)    return null;
        ListNode p1 = head,p2 = head;
        //如果存在环,那么让p1,p2同时指向相遇节点,如果没有环,那么p2最终会破坏循环条件
        while(p2 != null && p2.next != null){
            
            p1 = p1.next;
            p2 = p2.next.next;
            if(p1 == p2)    break;
        }
        //让head和p1都往前走,如果有换,那么会在环入口碰面,如果没有环,那么会二者其中一个会破坏循环条件
        while(head != null && p1 != null){
            if(head == p1)  return head;

                head = head.next;
                p1 = p1.next;
                        
        }
        return null; 
    }
}

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://hadoo666.top/archives/leetcode142环形链表iimd