142. Linked List Cycle II

栏目: Java · 发布时间: 5年前

内容简介:Given a linked list, return the node where the cycle begins. If there is no cycle, return null.To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

142. Linked List Cycle II

Example 2:

Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

142. Linked List Cycle II

Example 3:

Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

142. Linked List Cycle II

Follow up:

Can you solve it without using extra space?

难度:medium

题目:给定一链表,返回环的起始结点。如果无环返回空。为了表示链表中的环,使用整数来表示起如结点位置即尾结点所指向的位置。如果位置为-1则表示无环。

注意:不要修改链表。

思路:快慢指针。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Linked List Cycle II.

Memory Usage: 35.2 MB, less than 100.00% of Java online submissions for Linked List Cycle II.

/**
 * 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) {
        if (null == head) {
            return head;
        }
        ListNode slow = head, fast = head;
        do {
            slow = slow.next;
            fast = fast.next;
            fast = (fast != null) ? fast.next : fast;
        } while (fast != null && slow != fast);
        if (null == fast) {
            return null;
        }
        for (slow = head; slow != fast; slow = slow.next, fast = fast.next);
        
        return slow;
    }
}

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

程序员面试宝典(第5版)

程序员面试宝典(第5版)

欧立奇、刘洋、段韬 / 电子工业出版社 / 2015-10 / 55.00

容提要 《程序员面试宝典(第5版)》是《程序员面试宝典》的第5 版,在保留第4 版的数据结构、面向对象、程序设计等主干的基础上,修正了前4 版近40 处错误,解释清楚一些读者提出的问题,并使用各大IT 公司及相关企业最新面试题(2014-2015)替换和补充原内容,以反映自第4 版以来两年多的时间内所发生的变化。 《程序员面试宝典(第5版)》取材于各大公司面试真题(笔试、口试、电话面试......一起来看看 《程序员面试宝典(第5版)》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

随机密码生成器
随机密码生成器

多种字符组合密码

URL 编码/解码
URL 编码/解码

URL 编码/解码