力扣刷题:单链表OJ篇(下)-LMLPHP


1.环形链表

(1)题目描述

力扣刷题:单链表OJ篇(下)-LMLPHP
力扣刷题:单链表OJ篇(下)-LMLPHP


(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)题目描述

力扣刷题:单链表OJ篇(下)-LMLPHP
力扣刷题:单链表OJ篇(下)-LMLPHP


(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;
}

(3)复杂度分析


快乐的时光总是短暂,咱们下篇博文再见啦!!!如果小编的文章会对你有帮助的话不要忘了,记得给小编点赞、收藏支持一下,在此非常感谢!!!

12-29 07:31