目錄

1.鏈表的中間節(jié)點

2.鏈表中倒數(shù)第k個節(jié)點?

1.鏈表的中間節(jié)點

思路1：遍歷鏈表，統(tǒng)計節(jié)點個數(shù)count，返回第count/2 +1個節(jié)點?

??Note:注意循環(huán)條件為--mid，--mid循環(huán)執(zhí)行mid-1次，mid--循環(huán)mid次，返回的是中間節(jié)點的下一個節(jié)點

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* cur = head;
    int count = 0;
    //統(tǒng)計節(jié)點個數(shù)
    while(cur)
    {
        count++;
        cur = cur->next;
    }
    //返回第count/2+1個節(jié)點
    cur = head;
    int mid = count/2 + 1;
    while(--mid)
    {
        cur = cur->next;
    }

    return cur;

}

思路二：快慢指針

設置一個慢指針slow，一個快指針fast，慢指針一次走一步，快指針一次走兩步

需要分兩種情況：鏈表節(jié)點個數(shù)為奇數(shù)個和節(jié)點個數(shù)為偶數(shù)個

1??奇數(shù)個的情況

當鏈表節(jié)點個數(shù)為奇數(shù)個時，可以發(fā)現(xiàn)，快指針fast->next == NULL時，遍歷結束，此時慢指針slow剛好指向中間節(jié)點

2??偶數(shù)個的情況：

當鏈表節(jié)點個數(shù)為偶數(shù)個時，可以發(fā)現(xiàn)，快指針fast?== NULL時，遍歷結束，此時慢指針slow剛好指向中間節(jié)點

?綜上：遍歷結束的條件為fast == NULL或fast->next == NULL

參考代碼如下：文章來源地址http://www.zghlxwxcb.cn/news/detail-610808.html

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode* fast = head;
    struct ListNode* slow = head;

    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;

}

2.鏈表中倒數(shù)第k個節(jié)點?

與上題思路二相似的還有下例?

分析：

輸出鏈表中倒數(shù)第k個節(jié)點，假設有一個指針指向鏈表尾節(jié)點的next，即指向NULL，我們從這個節(jié)點向前看，尾節(jié)點相對這個指針來說是第一個節(jié)點，相對鏈表頭指針head來說便是倒數(shù)第一個節(jié)點，對于倒數(shù)第k個節(jié)點，指向這個節(jié)點的指針和指向NULL的指針始終相差的是k個節(jié)點；設置一個快指針fast，一個慢指針slow，fast指針先走k步，slow指針不動，此時fast指針和slow指針就相差k個節(jié)點，然后slow指針和fast指針同時向后走，直到fast指針指向NULL，此時slow指向的節(jié)點就是倒數(shù)第k個節(jié)點

以輸出倒數(shù)第三個節(jié)點為例，步驟如下圖：

??特殊情況討論：

1??空鏈表：返回空指針

2??倒數(shù)第一個

由上圖可以發(fā)現(xiàn)，輸出倒數(shù)第一個節(jié)點的邏輯與輸出倒數(shù)的k個節(jié)點的邏輯相同?

3??倒數(shù)第N個（鏈表長度為N）

由上圖可以發(fā)現(xiàn)，輸出倒數(shù)第N個節(jié)點的邏輯與輸出倒數(shù)的k個節(jié)點的邏輯相同?

4??k=0或k>N（N為鏈表的長度）

• k=0時，輸出鏈表的倒數(shù)第0個節(jié)點，應該為空

此時fast指針和slow指針都不會發(fā)生變化，，所以

• k>N時，fast先走k步會發(fā)生空指針的訪問

在fast指針向后走k步的過程中，需要隨時檢查fast指針的有效性，如果fast==NULL,直接返回空指針即可

參考代碼如下：

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) {
    // write code here
    struct ListNode* slow = pListHead,*fast = pListHead;
    if(pListHead)
    {
        while(k--)
        {
            if(fast == NULL)
            {
                return fast;
            }
            fast = fast->next;
        }
        while(fast)
        {
            slow = slow->next;
            fast = fast->next;
        }
    }

    return slow;

}

到了這里，關于【leetcode】鏈表的中間節(jié)點|鏈表中倒數(shù)第k個節(jié)點的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！