Skip to content

Commit fa448ed

Browse files
CoderDreamCoderDream
committed
解法二：快慢指针解法
解法二：快慢指针解法 1.定义快慢两个指针 slow=head; fast=head.next; 2.遍历链表 快指针步长为2：fast = fast.next.next; 慢指针步长为1：slow = slow.next; 3.当且仅当快慢指针重合，有环，返回true 4.快指针为null，或其next指向null，没有环，返回false，操作结束
1 parent 4bdc3fc commit fa448ed

11 files changed

+269
-189
lines changed

‎hello-algo/lagou-algo/leetcode-question/src/main/java/com/shuzijun/leetcode/editor/cn/Lc141LinkedListCycle.java

Lines changed: 143 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,143 @@
1+
//给你一个链表的头节点 head ，判断链表中是否有环。
2+
//
3+
// 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到
4+
//链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
5+
//
6+
// 如果链表中存在环 ，则返回 true 。 否则，返回 false 。
7+
//
8+
//
9+
//
10+
// 示例 1：
11+
//
12+
//
13+
//
14+
//
15+
//输入：head = [3,2,0,-4], pos = 1
16+
//输出：true
17+
//解释：链表中有一个环，其尾部连接到第二个节点。
18+
//
19+
//
20+
// 示例 2：
21+
//
22+
//
23+
//
24+
//
25+
//输入：head = [1,2], pos = 0
26+
//输出：true
27+
//解释：链表中有一个环，其尾部连接到第一个节点。
28+
//
29+
//
30+
// 示例 3：
31+
//
32+
//
33+
//
34+
//
35+
//输入：head = [1], pos = -1
36+
//输出：false
37+
//解释：链表中没有环。
38+
//
39+
//
40+
//
41+
//
42+
// 提示：
43+
//
44+
//
45+
// 链表中节点的数目范围是 [0, 10⁴]
46+
// -10⁵ <= Node.val <= 10⁵
47+
// pos 为 -1 或者链表中的一个 有效索引 。
48+
//
49+
//
50+
//
51+
//
52+
// 进阶：你能用 O(1)（即，常量）内存解决此问题吗？
53+
//
54+
// Related Topics 哈希表 链表 双指针 👍 2144 👎 0
55+
56+
57+
package com.shuzijun.leetcode.editor.cn;
58+
59+
/**
60+
* @author CoderDream
61+
*/
62+
public class Lc141LinkedListCycle {
63+
64+
public static void main(String[] args) {
65+
Solution solution = new Lc141LinkedListCycle().new Solution();
66+
ListNode l1 = new Lc141LinkedListCycle().new ListNode(3);
67+
ListNode l2 = new Lc141LinkedListCycle().new ListNode(2);
68+
ListNode l3 = new Lc141LinkedListCycle().new ListNode(0);
69+
ListNode l4 = new Lc141LinkedListCycle().new ListNode(-4);
70+
l1.next = l2;
71+
l2.next = l3;
72+
l3.next = l4;
73+
l4.next = l2;
74+
75+
Boolean result = solution.hasCycle(l1);
76+
System.out.println("result: " + result);
77+
}
78+
79+
//leetcode submit region begin(Prohibit modification and deletion)
80+
81+
/**
82+
* Definition for singly-linked list. class ListNode { int val; ListNode next; ListNode(int x) { val = x; next =
83+
* null; } }
84+
*/
85+
public class Solution {
86+
87+
/**
88+
* <pre>
89+
* 解法二：快慢指针解法
90+
* 1.定义快慢两个指针
91+
* slow=head; fast=head.next;
92+
* 2.遍历链表
93+
* 快指针步长为2：fast = fast.next.next;
94+
* 慢指针步长为1：slow = slow.next;
95+
* 3.当且仅当快慢指针重合，有环，返回true
96+
* 4.快指针为null，或其next指向null，没有环，返回false，操作结束
97+
*
98+
* </pre>
99+
*
100+
* @param head
101+
* @return
102+
*/
103+
public boolean hasCycle(ListNode head) {
104+
if (head == null) { // 链表中有节点[0, 10^4]个
105+
return false;
106+
}
107+
108+
// 1.定义快慢两个指针
109+
ListNode slow = head;
110+
ListNode fast = head.next;
111+
112+
// 2.遍历链表
113+
while (fast != null && fast.next != null) {
114+
// 3.当且仅当快慢指针重合，有环，返回true
115+
if (slow == fast) { // 重合比较，指针指向同一个地址，所以可以用等号
116+
return true;
117+
}
118+
119+
// 迭代
120+
fast = fast.next.next; // 快指针步长为2：fast = fast.next.next;
121+
slow = slow.next; // 慢指针步长为1：slow = slow.next;
122+
} // 4.快指针为null，或其next指向null，没有环，返回false，操作结束
123+
124+
return false;
125+
}
126+
}
127+
128+
//leetcode submit region end(Prohibit modification and deletion)
129+
class ListNode {
130+
131+
int val;
132+
ListNode next;
133+
134+
ListNode() {
135+
}
136+
137+
ListNode(int x) {
138+
val = x;
139+
next = null;
140+
}
141+
}
142+
143+
}

‎hello-algo/lagou-algo/leetcode-question/src/main/java/com/shuzijun/leetcode/editor/cn/LinkedListCycle141.java

Lines changed: 0 additions & 169 deletions
This file was deleted.

‎hello-algo/lagou-algo/leetcode-question/src/main/java/com/shuzijun/leetcode/editor/cn/doc/content/LC141LinkedListCycle.md

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
<p>给你一个链表的头节点 <code>head</code> ，判断链表中是否有环。</p>
2+
3+
<p>如果链表中有某个节点，可以通过连续跟踪 <code>next</code> 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 <code>pos</code> 来表示链表尾连接到链表中的位置（索引从 0 开始）。<strong>注意：<code>pos</code> 不作为参数进行传递&nbsp;</strong>。仅仅是为了标识链表的实际情况。</p>
4+
5+
<p><em>如果链表中存在环</em>&nbsp;，则返回 <code>true</code> 。 否则，返回 <code>false</code> 。</p>
6+
7+
<p>&nbsp;</p>
8+
9+
<p><strong>示例 1：</strong></p>
10+
11+
<p><img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist.png" /></p>
12+
13+
<pre>
14+
<strong>输入：</strong>head = [3,2,0,-4], pos = 1
15+
<strong>输出：</strong>true
16+
<strong>解释：</strong>链表中有一个环，其尾部连接到第二个节点。
17+
</pre>
18+
19+
<p><strong>示例&nbsp;2：</strong></p>
20+
21+
<p><img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist_test2.png" /></p>
22+
23+
<pre>
24+
<strong>输入：</strong>head = [1,2], pos = 0
25+
<strong>输出：</strong>true
26+
<strong>解释：</strong>链表中有一个环，其尾部连接到第一个节点。
27+
</pre>
28+
29+
<p><strong>示例 3：</strong></p>
30+
31+
<p><img alt="" src="https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2018/12/07/circularlinkedlist_test3.png" /></p>
32+
33+
<pre>
34+
<strong>输入：</strong>head = [1], pos = -1
35+
<strong>输出：</strong>false
36+
<strong>解释：</strong>链表中没有环。
37+
</pre>
38+
39+
<p>&nbsp;</p>
40+
41+
<p><strong>提示：</strong></p>
42+
43+
<ul>
44+
<li>链表中节点的数目范围是 <code>[0, 10<sup>4</sup>]</code></li>
45+
<li><code>-10<sup>5</sup> &lt;= Node.val &lt;= 10<sup>5</sup></code></li>
46+
<li><code>pos</code> 为 <code>-1</code> 或者链表中的一个 <strong>有效索引</strong> 。</li>
47+
</ul>
48+
49+
<p>&nbsp;</p>
50+
51+
<p><strong>进阶：</strong>你能用 <code>O(1)</code>（即，常量）内存解决此问题吗？</p>
52+
53+
<div><div>Related Topics</div><div><li>哈希表</li><li>链表</li><li>双指针</li></div></div><br><div><li>👍 2144</li><li>👎 0</li></div>

0 commit comments

Comments
 (0)