C\C++刷題DAY5-創(chuàng)新互聯(lián)

目錄

10年積累的成都網(wǎng)站設(shè)計、成都做網(wǎng)站經(jīng)驗，可以快速應(yīng)對客戶對網(wǎng)站的新想法和需求。提供各種問題對應(yīng)的解決方案。讓選擇我們的客戶得到更好、更有力的網(wǎng)絡(luò)服務(wù)。我雖然不認識你，你也不認識我。但先網(wǎng)站設(shè)計后付款的網(wǎng)站建設(shè)流程，更有七星關(guān)區(qū)免費網(wǎng)站建設(shè)讓你可以放心的選擇與我們合作。

1.第一題

2.第二題

3.第三題

---

1.第一題

160. 相交鏈表 - 力扣（LeetCode）

思路分析：

看鏈表相不相交，是看鏈表的地址。把兩個鏈表的地址一一比對，如有有相同的地址，那么相交，如果各不相同，那么肯定不相交。

但是如果要一一比對的話，時間復(fù)雜度是N^2,效果太差了。時間復(fù)雜度是N^2的原因是，有可能兩個鏈表的長度不一樣。假如兩個鏈表的長度一樣的話，就不需要一一比對了，只需要各自位置上的節(jié)點對比就行。這樣的話時間復(fù)雜度是N。

那么現(xiàn)在只要人讓長的先走，走到和短的一樣長，之后，長的短的一起走。這個時候再去對比地址，相同返回相交的節(jié)點，不同返回NULL

參考代碼：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    struct ListNode * curA = headA;
    struct ListNode * curB = headB;
    int lenA = 0;
    int lenB = 0;
    
    //找尾
    while(curA->next)
    {
        lenA++;
        curA =curA->next;
    }
     while(curB->next)
    {
        lenB++;
        curB =curB->next;
    }
    //尾節(jié)點不相等就相交
    if(curA!=curB)
        return NULL;
    
    int gap = abs(lenA-lenB);
    struct ListNode* longlist = headA;
    struct ListNode* shortlist = headB;
    if(lenB>lenA)
    {
        longlist=headB;
        shortlist=headA;
    }

    //長先走差距步
    while(gap--)
    {
        longlist = longlist->next;
    }

    //同時走，找交點
    while(longlist!=shortlist)
    {
        longlist =longlist->next;
        shortlist =shortlist->next;
    }
    return longlist;

}

2.第二題

141. 環(huán)形鏈表 - 力扣（LeetCode）

思路分析：

利用雙指針中的快慢指針，兩個指針一個走一步，一個走兩步，如果沒有環(huán)的話，就會走完整個鏈表，如果有環(huán)的話，那么兩個指針都會進入到環(huán)里面，在環(huán)里面的話，就會演變成一個追擊的問題，快的總會追上慢的。

由于快的走兩步，慢的走一步，那么快的相對比慢的速度就是1步，那么快的肯定會和慢的相遇，那么就能追上慢的。

（圖中為抽象的鏈表）

參考代碼：

bool hasCycle(struct ListNode *head)
{
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(fast == slow)
        return fast;
    }
    return NULL;
}

PS:思考，為什么設(shè)計成快的走2步？

為什么步設(shè)計成快的走3，4，5，6……步呢？

其實只要是有環(huán)的話，快的和慢的都會進入環(huán)中，那么假如快的走3步的話，那么和慢的的速度差就是2步，那么就有可能會越過慢的，只要當慢的和快的之間的節(jié)點數(shù)只差是奇數(shù)的話，那么快的總是會越過慢的

3.第三題

142. 環(huán)形鏈表 II - 力扣（LeetCode）

思路分析:

現(xiàn)在要求的是入環(huán)點，

先上結(jié)論：從頭節(jié)點走到入環(huán)點的距離就是相交點走到入環(huán)點的距離。

前提條件：相交點必須是快慢指針的相交點（也就是第二題中的），快指針一次走兩步，滿指針一次走一步。那么到相交的時候快指針走的距離就是慢指針走的距離的兩倍。

具體的結(jié)論分析看下圖：

第二種思路：

將鄉(xiāng)遇點meet置空，然后otherhead作為第二個頭節(jié)點，那么這個問題可以看成是兩個鏈表的相交問題，相交點就是之前的入環(huán)點。?

第一種思路的參考代碼：

struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(fast == slow)
        {
            struct ListNode * meet = slow;
            while(head != meet)
            {
                head=head->next;
                meet=meet->next;
            }
            return meet;
        }
       
    }
    return NULL;
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

新聞名稱：C\C++刷題DAY5-創(chuàng)新互聯(lián)
URL標題：http://m.jiaotiyi.com/article/dgddcj.html