leetcode刷题（38）——142. 环形链表 II

老马的编程之旅

发布于 2022-06-22 13:34:11

1730

发布于 2022-06-22 13:34:11

文章被收录于专栏：深入理解Android

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

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

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

示例 1：

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

解法1:还是先用快慢指针找出是否是环形链表，同时记住停下来的节点fast,然后另一个指针从头节点开始出发，2个指针都移动1步，最后相遇的地方的节点就是环形链表的开始

public class Solution {
    public ListNode detectCycle(ListNode head) {
           if(head==null){
                return null;
            }
            ListNode in = getIntersect(head);
            if (in==null){
                return null;
            }
            ListNode p1 = head;
            ListNode p2 = in;
            while (p1!=p2){
                p1=p1.next;
                p2=p2.next;
            }
            return p1;

    }
    
     private ListNode getIntersect(ListNode head){
            ListNode fast = head;
            ListNode slow = head;
            while (fast!=null&&fast.next!=null){
                fast = fast.next.next;
                slow = slow.next;
                if (fast==slow){
                    return fast;
                }
            }
            return null;
        }
}

需要注意几个点： 1.抽象出getIntersect方法来获取快的ListNode 2.getIntersect方法返回的对象需要判空

  ListNode in = getIntersect(head);
            if (in==null){
                return null;
            }

解法2:使用set集合存放经历过的节点，循环中第一个在set里的节点一定是环形的入口

public class Solution {
    public ListNode detectCycle(ListNode head) {
          Set<ListNode> visited = new HashSet<ListNode>();

        ListNode node = head;
        while (node != null) {
            if (visited.contains(node)) {
                return node;
            }
            visited.add(node);
            node = node.next;
        }

        return null;

    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020-01-24，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法