侧边栏壁纸
博主头像
阿里灰太狼博主等级

You have to believe in yourself . That's the secret of success.

  • 累计撰写 104 篇文章
  • 累计创建 50 个标签
  • 累计收到 12 条评论

目 录CONTENT

文章目录

leetcode-142. 环形链表 II

阿里灰太狼
2022-09-16 / 0 评论 / 0 点赞 / 573 阅读 / 720 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-09-16,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

142. 环形链表 II0
142. 环形链表 II1

JAVA解法(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) {
        // 定义一个 HashSet 集合,利用的是 set 不可重复的性质
        HashSet<ListNode> set = new HashSet<>();
        // 新建一个节点 cur
        ListNode cur = new ListNode(0);
        // 将 cur 节点指向传进来链表的头节点 head
        cur.next = head;
        // 用 while 循环将链表上每一个不同节点都逐一加入 set 中
        while(set.add(cur) != false){
            // 若到了链表尾部,则说明不存在环
            if(cur == null){
                return null;
            }
            // 若正常则继续往下
            cur = cur.next;
        }
        // 返回起冲突的节点,此时这个节点就是环的第一个节点
        return cur;
    }
}

题解分析(HashSet 解法)

  根据题目要求,我们可以想到可以利用 set 不可重复的性质来完成这道题。定义一个 HashSet 集合且新建一个节点 cur 并让 cur 指向传进来链表的头节点 head,用 while 循环将链表上每一个点都逐一加入 set 中,只要不重复且不到链表尾部,都可以正常加入 set 中,若到了链表尾部都没有冲突出现,则证明这个链表不含环,若出现冲突,则说明含环,并返回起冲突的节点,此时这个节点就是环的第一个节点。


JAVA解法(快慢指针解法)

/**
 * 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) {
        // 定义快慢指针
        ListNode fast = head;
        ListNode slow = head;
        // 在不到链表尾的情况下循环
        while (fast != null && fast.next != null) {
            // 快指针走两步,慢指针走一步
            fast = fast.next.next;
            slow = slow.next;
            // 若快指针跟慢指针相遇则说明有环
            if (fast == slow) {
                // 让快指针从头开始,每次走一步
                fast = head;
                // 当同速度的指针相遇,此时该点为环的起点,返回即可
                while (fast != slow) {
                    fast = fast.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        // 找不到环返回空
        return null;
    }
}

题解分析(快慢指针解法)

  根据题目要求,我们也可以用快慢指针解这道题。先定义快慢指针,在不到链表尾的情况下循环,快指针走两步,慢指针走一步,若快指针跟慢指针相遇则说明有环,让快指针从头开始,每次走一步,慢指针在相遇点继续以原来的速度走,当同速度的指针相遇,则根据路程一致原理,此时该点为环的起点,返回即可。

参考:算法解析:通过快慢指针判断链表是否存在环并找到环的起点

leetcode原题:142. 环形链表 II

0

评论区