欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

链表——找到入环第一个节点

程序员文章站 2022-05-04 14:23:49
链表——找到入环第一个节点(Leetcode.142)题目:给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 null。说明:不允许修改给定的链表。1、笔试(额外容器)笔试:使用额外容器——HashSet由于单链表只有一个next指针,所以如果一个单链表在某一节点入环了,那么它就不可能再跳出这个环了利用 HashSet 的元素唯一性,根据 next 指针指向将节点依次存入 set,当判断 set 中有重复节点的时候。即为第一个入环节点使用hashset结构,时间复杂度O(N...

链表——找到入环第一个节点(Leetcode.142)

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

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

1、笔试(额外容器)

笔试:使用额外容器——HashSet

  • 由于单链表只有一个next指针,所以如果一个单链表在某一节点入环了,那么它就不可能再跳出这个环了
  • 利用 HashSet 的元素唯一性,根据 next 指针指向将节点依次存入 set,当判断 set 中有重复节点的时候。即为第一个入环节点
  • 使用hashset结构,时间复杂度O(N),额外空间复杂度O(N)

代码实现:

public class GetLoopNode {
    public static class ListNode{
        int val;
        ListNode next;

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

    public ListNode detectCycle(ListNode head) {
        ListNode loopNode = null;

        ListNode curNode = head;
        LinkedList<ListNode> listNodes = new LinkedList<ListNode>();

        while (curNode != null){
            if (!listNodes.contains(curNode)){
                listNodes.add(curNode);
                curNode = curNode.next;
            }else {
                loopNode = curNode;
                break;
            }
        }
        return loopNode;
    }
}

2、面试(快慢指针)

面试:使用快慢指针

  1. 如果head为null,或者长度为1,或者无环,都应该返回 null;
  2. 如果存在环,快指针就会首先进入环,并不断在环内循环,且一定会在某处遇到慢指针;
  3. 相遇之时,用另外一个指针从 head 开始出发,和慢指针一起一次走一步,最终此指针和慢指针相交位置就是第一个入环节点;
  4. 关于追及问题,好像是小学奥赛题。数学推导证明:https://leetcode-cn.com/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/

代码实现:

public class GetLoopNode {
    public static class ListNode{
        int val;
        ListNode next;

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

 
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null){
            return null;
        }

        ListNode fast = head;
        ListNode slow = head;

        while (fast != null){
            slow = slow.next;
            
            //如果 fast 走向 null,说明必然无环
            if (fast.next != null){
                fast = fast.next.next;
            }else {
                return null;
            }

            //如果存在相交节点,则必然存在环,找到入环节点即可
            if (fast == slow){
                ListNode ptr = head;
                while (ptr != slow){
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }

        return null;
    }

}

本文地址:https://blog.csdn.net/qq_42583242/article/details/109561077