LC-141和LC-142有哪些区别？
- 内容介绍
- 文章标签
- 相关推荐
本文共计656个文字，预计阅读时间需要3分钟。
142. 简化环形链表 II 思路：设链表共有 a+b 个节点，其中从链表头部到入口有 a 个节点（不包括入口节点），环中有 b 个节点。再设两个指针分别指向 f 和 s，分别从入口和头部出发，同时移动。则有两种情况：
1.f 和 s 相遇时，f 所走过的距离为 f=2s
2.s 到达尾部，此时 f 也到达尾部，f 所走过的距离为 2s=2s
142. 环形链表 II思路：
设链表共有 a+b 个节点，其中 链表头部到链表入口 有 a 个节点（不计链表入口节点）， 链表环 有 b 个节点。
再设两指针分别走了 f，s 步，则有：
- f = 2sf=2s；
- fast 比 slow多走了 n 个环的长度，即 f = s + nbf=s+nb；
- 以上两式相减得：f = 2nbf=2nb，s = nbs=nb；
概括一下：
根据：
- f=2s （快指针每次2步，路程刚好2倍）
- f = s + nb (相遇时，刚好多走了n圈）
推出：s = nb
从head结点走到入环点需要走 ： a + nb， 而slow已经走了nb，那么slow再走a步就是入环点了。
如何知道slow刚好走了a步？ 从head开始，和slow指针一起走，相遇时刚好就是a步。
Java实现
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head, slow = head;
while(true) {
if(fast == null || fast.next == null) return null;
fast = fast.next.next;
slow = slow.next;
if(fast == slow) break;
}
fast = head;
while (fast != slow){
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
Python实现
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def detectCycle(self, head):
fast, slow = head, head
while True:
if not (fast and fast.next): return
fast, slow = fast.next.next, slow.next
if fast == slow: break
fast = head
while fast != slow:
fast, slow = fast.next, slow.next
return fast
141. 环形链表
142少去算法部分。单纯用快慢指针判断是否相遇即刻。
Java实现
/**
* 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) {
ListNode fast = head, slow = head;
while(true) {
if(fast == null || fast.next == null) return false;
fast = fast.next.next;
slow = slow.next;
if(fast == slow) return true;
}
}
}
Python实现
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
fast, slow = head, head
while True:
if not (fast and fast.next): return False
fast = fast.next.next
slow = slow.next
if fast == slow: return True
本文共计656个文字，预计阅读时间需要3分钟。
142. 简化环形链表 II 思路：设链表共有 a+b 个节点，其中从链表头部到入口有 a 个节点（不包括入口节点），环中有 b 个节点。再设两个指针分别指向 f 和 s，分别从入口和头部出发，同时移动。则有两种情况：
1.f 和 s 相遇时，f 所走过的距离为 f=2s
2.s 到达尾部，此时 f 也到达尾部，f 所走过的距离为 2s=2s
142. 环形链表 II思路：
设链表共有 a+b 个节点，其中 链表头部到链表入口 有 a 个节点（不计链表入口节点）， 链表环 有 b 个节点。
再设两指针分别走了 f，s 步，则有：
- f = 2sf=2s；
- fast 比 slow多走了 n 个环的长度，即 f = s + nbf=s+nb；
- 以上两式相减得：f = 2nbf=2nb，s = nbs=nb；
概括一下：
根据：
- f=2s （快指针每次2步，路程刚好2倍）
- f = s + nb (相遇时，刚好多走了n圈）
推出：s = nb
从head结点走到入环点需要走 ： a + nb， 而slow已经走了nb，那么slow再走a步就是入环点了。
如何知道slow刚好走了a步？ 从head开始，和slow指针一起走，相遇时刚好就是a步。
Java实现
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast = head, slow = head;
while(true) {
if(fast == null || fast.next == null) return null;
fast = fast.next.next;
slow = slow.next;
if(fast == slow) break;
}
fast = head;
while (fast != slow){
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
Python实现
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def detectCycle(self, head):
fast, slow = head, head
while True:
if not (fast and fast.next): return
fast, slow = fast.next.next, slow.next
if fast == slow: break
fast = head
while fast != slow:
fast, slow = fast.next, slow.next
return fast
141. 环形链表
142少去算法部分。单纯用快慢指针判断是否相遇即刻。
Java实现
/**
* 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) {
ListNode fast = head, slow = head;
while(true) {
if(fast == null || fast.next == null) return false;
fast = fast.next.next;
slow = slow.next;
if(fast == slow) return true;
}
}
}
Python实现
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
fast, slow = head, head
while True:
if not (fast and fast.next): return False
fast = fast.next.next
slow = slow.next
if fast == slow: return True