目录
1.环形链表
(1)题目描述
(2)解题思路
代码实现:
bool hasCycle(struct ListNode *head) {
//快慢指针看是否会相遇,但最好快指针一次走两步,慢指针一次走一步,就不会出现有环却不相遇的情况
struct ListNode* fast = head, * slow = head;
if(head == NULL) return false;
while(fast && fast->next){
fast = fast->next->next;
slow = slow->next;
if(fast == slow){
return true;
}
}
return false;
}
(3)复杂度分析
2.环形链表2
(1)题目描述
(2)解题思路
代码实现:
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
if (headA == NULL || headB == NULL) {
return NULL;
}
struct ListNode *p1 = headA, *p2 = headB;
while (p1 != p2) {
p1 = p1 == NULL ? headB : p1->next;
p2 = p2 == NULL ? headA : p2->next;
}
return p1;
}
struct ListNode *detectCycle(struct ListNode *head) {
if (head == NULL) return NULL;
struct ListNode* fast = head, * slow = head;
while (fast && fast->next) {
//先走,防止因为头指针相等
fast = fast->next->next;
slow = slow->next;
if (fast == slow) {
struct ListNode* ptr = fast->next;
fast->next = NULL;
return getIntersectionNode(ptr, head);
}
}
return NULL;
}
代码实现:
struct ListNode *detectCycle(struct ListNode *head) {
//这题要做出就一定要推出一个定理:两个快慢指针他们相交于环内一位置,而一指针从该位置开始走,同时另一从链表的头结点开始走,它们最终会第一次相交于环开始的那个节点。(怎么得到这个定理的一定要掌握,因为HR问到会问这个)
struct ListNode* fast = head, * slow = head;
if (head == NULL) return NULL;
while (fast && fast->next) {
//先走,防止因为头指针相等
fast = fast->next->next;
slow = slow->next;
if (fast == slow) {
struct ListNode* ptr = head;
while(ptr != slow){
ptr = ptr->next;
slow = slow->next;
}
return ptr;
}
}
return NULL;
}