Leetcode日记:141&142.链表中的环

141题目:判断是否存在环

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:

1
2
3
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

!(leetcode141-1.png)

Example 2:

1
2
3
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

!(leetcode141-2.png)

Example 3:

1
2
3
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

!(leetcode141-3.png)

141问题分析

这道题意思很简单,判断输入的链表是否存在环。
上次刚讲到快慢指针的应用问题,这次就遇到了链表中的环。那么如何将二者结合起来呢?

其实答案很简单,快指针一下走两步,慢指针一下走一步,如果链表存在环,那么快慢指针一定会在环的某个位置相遇

141代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public boolean hasCycle(ListNode head) {
ListNode slow = new ListNode(0);
ListNode fast = new ListNode(0);
slow.next = head;
fast.next = head;
if(head==null)
return false;
while(fast!=null&&fast.next!=null){
//如果快慢指针相遇,说明存在环
if(slow==fast)
return true;
slow = slow.next;
fast = fast.next.next;
}
return false;
}

142题目:找出链表中环的起始位置

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

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.

!(leetcode141-1.png)
Example 2:

1
2
3
Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.

!(leetcode141-2.png)
Example 3:

1
2
3
Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.

!(leetcode141-3.png)

142题目分析

这道题在141的基础上多了一个找出环的初始位置,这个需要用到一个常识或者说小技巧,我们要知道。
快慢指针相遇的位置和环起点的位置,以及链表头节点位置关系:

第一次碰撞点Pos到连接点Join的距离=头指针到连接点Join的距离,因此,分别从第一次碰撞点 Pos、头指针 head 开始走,相遇的那个点就是连接点。

circle
circle

在环上相遇后,记录第一次相遇点为 Pos,连接点为 Join,假设头结点到连接点的长度为LenA,连接点到第一次相遇点的长度为x,环长为 R。
第一次相遇时,slow 走的长度 S = LenA + x;
第一次相遇时,fast 走的长度 2S = LenA + n*R + x;
所以可以知道,LenA + x = n*R;  LenA = n*R -x;

142代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public ListNode detectCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast!=null && fast.next!=null){
fast = fast.next.next;
slow = slow.next;
//相遇之后,从头节点出发
if (fast == slow){
ListNode slow2 = head;
while (slow2 != slow){
slow = slow.next;
slow2 = slow2.next;
}
return slow;
}
}
return null;
}

补充:求有环单链表的环长

在环上相遇后,记录第一次相遇点为Pos,之后指针slow继续每次走1步,fast每次走2步。在下次相遇的时候fast比slow正好又多走了一圈,也就是多走的距离等于环长。

circle
circle

设从第一次相遇到第二次相遇,设slow走了len步,则fast走了 2*len 步,相遇时多走了一圈:环长 = 2*len-len。

更多关于链表的问题

更多关于链表的问题请转到链表标签