【数据结构与算法 | 基础篇】[链表专题]力扣141, 142

简介: 【数据结构与算法 | 基础篇】[链表专题]力扣141, 142

1. 力扣141 : 环形链表

题 :


给你一个链表的头节点 head ,判断链表中是否有环。


如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。注意: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)(即,常量)内存解决此问题吗?

思路 : 如果是空链表,直接返回false.如果是环形链表,那么p以及p.next一定不为null.p的移动速度比q快.所以p一定会追赶上q(p==q).所以此时返回true.否则返回flase.

解 :

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        ListNode p = head;
        ListNode q = head;
        while(p != null && p.next != null) {
            p = p.next.next;
            q = q.next;
            if (p == q) {
                return true;
            }
        }
        return false;
    }
}

2. 力扣142 : 环形链表2

题 :

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


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


不允许修改 链表。

示例 1:

输入:head = [3,2,0,-4], pos = 1

输出:返回索引为 1 的链表节点

解释:链表中有一个环,其尾部连接到第二个节点。


示例 2:

输入:head = [1,2], pos = 0

输出:返回索引为 0 的链表节点

解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:

输入:head = [1], pos = -1

输出:返回 null

解释:链表中没有环。

提示:

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


进阶:你是否可以使用 O(1) 空间解决此题?

思路 :

解 :

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode p = head;
        ListNode q = head;
        while (p != null && p.next != null) {
            p = p.next.next;
            q = q.next;
            if (p == q) {
                q = head;
                while(q != p) {
                    p = p.next;
                    q = q.next;
                }
                return p;
                
            }
        }
        return null;
    }
}
相关文章
|
2天前
|
Java Python
二刷力扣--链表
二刷力扣--链表
|
2天前
数据结构 链表(第7、8天)
数据结构 链表(第7、8天)
|
2天前
|
存储 算法 调度
力扣中级算法(Python)
力扣中级算法(Python)
|
2天前
|
算法 Python
力扣初级算法(Python)(二)
力扣初级算法(Python)(二)
|
2天前
|
算法 Python
力扣初级算法(Python)(一)
力扣初级算法(Python)(一)
|
2天前
|
存储
数据结构——带头双向循环链表
数据结构——带头双向循环链表
|
3天前
|
算法
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
【经典LeetCode算法题目专栏分类】【第7期】快慢指针与链表
|
5天前
|
存储
初阶数据结构 带头双链表
初阶数据结构 带头双链表
8 0
|
5天前
数据结构初阶 链表的补充
数据结构初阶 链表的补充
7 0
|
5天前
|
存储
数据结构初阶 链表详解
数据结构初阶 链表详解
7 0