力扣141和142分别是判断是否有环及环入口。
一个很好的解释:https://www.cnblogs.com/songdechiu/p/6686520.html
链表是否有环
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:
if not head:
return False
slow = fast = head
while slow and fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
Java
public class Solution {
public boolean hasCycle(ListNode 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;
}
}
链表环入口
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return None
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
if not fast or not fast.next: # 注意这个判断条件!!!
return None
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow
Java
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
break;
}
}
if (fast == null || fast.next == null) {
return null;
}
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
##Solution1:
非常经典的快慢指针套路题。下面这个链接讲解的很详细。其实问题的关键在于为什么快指针的速度一定是慢指针的2倍,3倍或4倍行不行??
快慢指针是一类很经典的算法,在这里贴一个讲解的比较清楚的博客:
https://www.cnblogs.com/songdechiu/p/6686520.html
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead) {
if(pHead == NULL || pHead->next == 0 || pHead->next->next == 0)
return NULL;
struct ListNode *slow = pHead->next, *fast = pHead->next->next; //slow走了1步到pHead->next的位置,fast走了2步
while(fast != slow) { //到了pHead->next->next的位置
if(fast->next != NULL && fast->next->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
else
return NULL;
}
struct ListNode *temp = pHead;
while(temp != slow) {
temp = temp->next;
slow = slow->next;
}
return temp;
}
};
##关于快指针速度的解释
https://blog.csdn.net/xgjonathan/article/details/18034825