LeetCode - 142. Linked List Cycle II

栏目: 编程工具 · 发布时间: 6年前

内容简介:Given a linked list, return the node where the cycle begins. If there is no cycle, returnNote: Do not modify the linked list.Follow up:

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

Note: Do not modify the linked list.

Follow up:

Can you solve it without using extra space?

快慢指针,参考 LeetCode - 141. Linked List Cycle

先判断是否有环,记录第一次相遇位置,然后快指针指向head指针,同步走,再次相遇时的节点即为环的入口。

证明:TODO

/**
 * 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 (head == null)
            return null;
        ListNode fast = head, slow = head;
        int cnt = 0;
        while (true) {
            if (fast == null)
                return null;
            if (cnt > 0 && fast == slow)
                break;
            slow = slow.next;
            fast = fast.next;
            if (slow == null || fast == null)
                return null;
            fast = fast.next;
            cnt ++;
        }
        fast = head;
        while (fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

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

Dive Into Python 3

Dive Into Python 3

Mark Pilgrim / Apress / 2009-11-6 / USD 44.99

Mark Pilgrim's Dive Into Python 3 is a hands-on guide to Python 3 (the latest version of the Python language) and its differences from Python 2. As in the original book, Dive Into Python, each chapter......一起来看看 《Dive Into Python 3》 这本书的介绍吧!

SHA 加密
SHA 加密

SHA 加密工具

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器