当前位置:   article > 正文

leetcode刷题:链表07 (环形链表 II)

leetcode刷题:链表07 (环形链表 II)

142.环形链表II

力扣题目链接

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

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

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

循环链表

package com.programmercarl.linkedlist;

import com.programmercarl.linkedlist.domain.ListNode;
import org.apache.bcel.generic.NEW;

/**
 * @ClassName DetectCycle
 * @Descriotion https://leetcode.cn/problems/linked-list-cycle-ii/
 * @Author nitaotao
 * @Date 2022/6/19 14:38
 * @Version 1.0
 * 环形链表 II
 **/
public class DetectCycle {
    public static void main(String[] args) {
        ListNode node4 = ListNode.builder().val(4).next(null).build();
        ListNode node3 = ListNode.builder().val(3).next(node4).build();
        ListNode node2 = ListNode.builder().val(2).next(node3).build();
        ListNode node1 = ListNode.builder().val(1).next(node2).build();
        node4.next = node2;
        System.out.println(detectCycle(node1).val);
    }

    /**
     * 给定一个链表的头节点 head,返回链表开始入环的第一个节点。如果链表无环,则返回null。
     * <p>
     * 如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
     * <p>
     * 不允许修改 链表。
     * <p>
     * 来源:力扣(LeetCode)
     * 链接:https://leetcode.cn/problems/linked-list-cycle-ii
     *
     * @param head
     * @return
     */
    public static ListNode detectCycle(ListNode head) {
        /**
         * 提示:
         * 链表中节点的数目范围在范围 [0, 10^4] 内
         * -10^5 <= Node.val <= 10^5
         * pos 的值为 -1 或者链表中的一个有效索引
         */
        //我打算从边界值入手
        if (head == null || head.next == null) {
            return null;
        }
        ListNode newHead = head;
        while (newHead.val < 100000 ) {
            newHead.val += 1000000;
            newHead = newHead.next;
            if (newHead == null) {
                return null;
            }
        }
        //此时的newHead就是要返回的结果结点
        ListNode resultNode = newHead;
        //此时所有遍历过的结点,值是>100000的
        newHead = head;
        while (newHead.val > 100000) {
            newHead.val -= 1000000;
            newHead = newHead.next;
        }
        return resultNode;
    }
}

  • 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
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67

有一说一还是标记法好用,不让修改链表,咱就改完再改回去。

在这里插入图片描述

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/笔触狂放9/article/detail/980630
推荐阅读
相关标签
  

闽ICP备14008679号