LeetCode_双指针_简单_141.环形链表

x33g5p2x  于2022-02-07 转载在 其他  
字(1.1k)|赞(0)|评价(0)|浏览(192)

1.题目

给你一个链表的头节点 head ,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
如果链表中存在环,则返回 true 。 否则,返回 false 。

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

示例 2:

输入:head = [1,2], pos = 0
输出:true
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

输入:head = [1], pos = -1
输出:false
解释:链表中没有环。

提示:
链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。

进阶: 你能用 O(1)(即,常量)内存解决此问题吗?

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/linked-list-cycle

2.思路

(1)双指针
① 定义快慢指针 fast 和 slow,初始时都指向head;
② 快慢指针同时出发开始遍历链表,其中,慢指针每次走一步,快指针每次走两步,如果快慢指针相遇,说明链表中存在环,直接返回 true 即可;
③ 快指针到达链表末尾时停止遍历,如果快慢指针没有相遇,说明链表中不存在环,最后返回 false 即可。

3.代码实现(Java)

//思路1————双指针
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        //定义快慢指针,初始时都指向head
        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;
    }
}

相关文章

微信公众号

最新文章

更多