有环链表

题意

给定一个链表,判断它是否有环。

样例

A:   1->5->10->11->18
           ↑       ↓
           ↑       ↓
           ↑ ← ← ← ←

A:   1->5->10->11->18->null

链表 A 的第五个节点 18 的 next 节点是 10,如此构成有环链表。

链表 B 则是一个无环链表。

思路

如果链表有环,可以把有环部分看成一个跑道,有两个人,一个跑的快,一个跑的慢,如此一直跑下去,跑的快的一定会追上跑的慢的。

如果链表无环,那么跑的快的那个一定会先到达链表尾部,也就是 NULL。

我们可以设置两个指针来模拟那两个跑的快的人和跑的慢的人,一个指针每次向后移动一位,另一个指针每次向后移动两位,直到两者相遇或快指针到达链表尾部。

代码实现

/**
 * Definition for ListNode.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int val) {
 *         this.val = val;
 *         this.next = null;
 *     }
 * }
 */ 
public class Solution {
    /**
     * @param head: The first node of linked list.
     * @return: True if it has a cycle, or false
     */
    public boolean hasCycle(ListNode head) { 
        if (head == null || head.next == null) {
            return false;
        }
        
        ListNode slow = head, fast = head;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }
}

原题地址

LintCode:带环链表

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏尾尾部落

[LeetCode]Merge Two Sorted Lists 合并两个排好序的链表 [LeetCode]Merge Two Sorted Lists 合并两个排好序的链表

链接:https://leetcode.com/problems/merge-two-sorted-lists/#/description 难度:Easy...

11220
来自专栏和蔼的张星的图像处理专栏

35. 翻转链表

样例 给出一个链表1->2->3->null,这个翻转后的链表为3->2->1->null

32330
来自专栏五分钟学算法

每天一算:Remove Linked List Elements

LeetCode上第203号问题:Remove Linked List Elements

9930
来自专栏书山有路勤为径

链表划分

LeetCode 86.Partition List 已知链表头节点指针head与数值X,将所有小于x的节点放在大于或等于x的节点前,且保持这些节点的原来的相...

8340
来自专栏赵俊的Java专栏

两两交换链表中的节点

30440
来自专栏机器学习入门

LWC 58:725. Split Linked List in Parts

LWC 58:725. Split Linked List in Parts 传送门:725. Split Linked List in Parts Probl...

22280
来自专栏书山有路勤为径

两个排序链表合并

LeetCode 21. Merge Two Sorted Lists 已知两个已排序链表头节点指针L1,L2,将这两个链表合并,合并后仍为有序的,返回合并后...

11330
来自专栏韦弦的偶尔分享

Swift 环形链表- LeetCode

可以转化为一个追击问题 前后双指针,slow走一步,fast走两步,如果有环存在,一定会相遇的。

15630
来自专栏chenjx85的技术专栏

leetcode-83-Remove Duplicates from Sorted List

20160
来自专栏desperate633

LeetCode 142. Linked List Cycle II题目分析代码

给定一个链表,如果链表中存在环,则返回到链表中环的起始节点的值,如果没有环,返回null。

10430

扫码关注云+社区

领取腾讯云代金券