当前位置:   article > 正文

判断单链表是否有环?以及入环节点

判断单链表是否有环

判断单链表是否有环?

问题概述

在这里插入图片描述
如果存在环就返回true,不存在就false
接下来我提供两种思路

  • 利用hash
  • 快慢指针

方案一:hash法

解题思路

这方法其实相对来说比较容易理解。大致思路就是:
遍历单链表,在遍历的时候,先判断当前节点索引是否在hash表中,如果不存在则将当前节点的索引存入到hash表中,如果当前节点索引已经存在于hash表中,则说明链表又绕回来了,说明链表有环,并且这个节点就是入环节点,直接返回true

代码实现

完整代码实现:

import java.util.HashMap;
/**
 * 单向链表类
 */
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }

    // 主方法测试
    public static void main(String[] args) {
        ListNode pHead = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        pHead.next = node2; node2.next = node3; node3.next = node4; node4.next = node5;
        node5.next = node3; // 这里成环了
        boolean hasCycle = hashCycle(pHead);
        System.out.println("是否存在环:"+hasCycle);
    }

    /**
     * 方案一 hash法
     * @param pHead
     * @return
     */
    public static boolean hashCycle(ListNode pHead) {
        ListNode cur = pHead;
        // 创建一个hash表
        HashMap<ListNode, Integer> hash = new HashMap<>();
        while (cur != null) {
            // 如果当前索引不在hash表中 则添加
            if (hash.get(cur) == null) {
                hash.put(cur, 1);
            } else {
                return true;
            }
            // 指针后移
            cur = cur.next;
        }
        // 如果能走出while循环 则说明该链表不存在环
        return false;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48

方案一:快慢指针法

解题思路

该方法是用快慢指针做,时间复杂度可以是O(1),效率很高。
如何用快慢指针来做呢?无非就是判断快慢两个指针最后是否会相遇,如果有环的话,快慢两个指针最后肯定会相遇。
用快慢指针来解决这个问题就好比龟兔赛跑一样,如果赛道是一个环的话兔子和乌龟最终都会相遇,最重要的是一快一慢(一般fast指针走2步,slow指针走1步),以及两个指针的速度最后取合适的值(若fast走其他大于2的步数,则当fast追slow时步数差减少有可能会错过0步,直接超过slow,当环数处于一个特殊值时两个指针可能永远不会相遇,每次将要相遇时fast将会直接超过slow)

代码实现

/**
 * 单向链表类
 */
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }

    // 主方法测试
    public static void main(String[] args) {
        ListNode pHead = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        ListNode node4 = new ListNode(4);
        ListNode node5 = new ListNode(5);
        pHead.next = node2; node2.next = node3; node3.next = node4; node4.next = node5;
        node5.next = node3; // 这里成环了
        boolean hasCycle = hashCycle(pHead);
        System.out.println("是否存在环:"+hasCycle);
    }

    /**
     * 方案一 快慢指针法
     * @param pHead
     * @return
     */
    public static boolean hashCycle(ListNode pHead) {
    	if(pHead == null) return false;
    	if(pHead.next == null) return false;
        ListNode slow = pHead.next;  // 慢指针,一次走一步
        ListNode fast = pHead.next.next;  // 快指针,一次走两步
        while (slow != fast) {
        	if(fast == null || fast.next == null) {
				return false;
			}
            slow = slow.next;   // 慢指针,一次走一步
            fast = fast.next.next;	// 快指针,一次走两步
        }
        // 如果跳出while循环 ,说明fast与slow相遇了, 也说明该链表存在环
        return true;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45

链表中环的入口结点

问题链接

【JZ23 链表中环的入口结点】

该题相当于是在上个问题的基础上加了一问,不仅要判断是否成环,还要返回成环的第一个节点,即入环节点

其实该题也可以用两种方式去做,hash和双指针。
hash的话,和上面判断是否成环?的代码差不多,不同的是,在返回结果时,直接返回节点索引即可,这里这部分代码我就不演示了,接下来我只讲解双指针这种思路的解法。

解题思路

在这里插入图片描述

我先说解题步骤:

  1. 首先快、慢指针都从起点开始向前走,快指针-fast每次走2步,慢指针-slow每次走1步
  2. 当他们相遇时(判断出有环),记下相遇点
  3. 然后快指针-fast从起点开始、慢指针-slow从相遇点开始,都以每次走1步的速度向前走。(其实这里只要保证一个指针从起点走,一个指针从相遇点走就可以了,并不一定非是fast指针从起点走)
  4. 当他们再次相遇时,这次的相遇点就是入环点

当然上面只是结论,其实这里是一个数学问题, 在他们第一次相遇时,由于快指针-fast的速度是慢指针-slow两倍因此快指针走的路程也是慢指针的2倍,因此可以建如下关系式
在这里插入图片描述
最后得出结论:a = (m-2n-1)(b+c)+c
也就是fast指针起点开始走到入环节点的路程,slow指针相遇点c的路程+整数圈环 一定刚好到达入环节点

代码实现

public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead) {
    	if(pHead == null) return null;
    	if(pHead.next == null) return null;
        ListNode slow = pHead.next;  // 慢指针,一次走一步
        ListNode fast = pHead.next.next;  // 快指针,一次走两步
        while (slow != fast) {
        	// 如果不存在环 就直接返回null
        	if(fast == null || fast.next == null) {
				return null;
			}
            slow = slow.next;   // 慢指针,一次走一步
            fast = fast.next.next;	// 快指针,一次走两步
        }
        // 快指针 或者 慢指针 从头结点出发(指针指向pHead),慢指针从相遇点出发(指针指向不变)
        slow = pHead;
        // 新一轮移动 一个指针从头结点 一个指针从相遇节点(哪个从头结点哪个从相遇点都无所谓)
        while(fast != slow) {
            // 快慢指针后移 每轮都走一步
            fast = fast.next;
            slow = slow.next;
        }
        // 当快慢指针再次相遇时 就是入环节点
        return fast; // 或者 return slow;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Monodyee/article/detail/604739
推荐阅读
相关标签
  

闽ICP备14008679号