leetcode 876.連結清單中間結點

連結清單中間結點

leetcode題目連結：876. 連結清單的中間結點

一、樸素解法

最直覺的思路，因為不知道這個連結清單的長度，就先通過一次循環統計連結清單的長度len

之後第二次周遊，直到找到中間結點，輸出

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
 
struct ListNode* middleNode(struct ListNode* head){
    struct ListNode *p = head;
    int len = 0, t = 0;
    // 統計連結清單長度len
    while(p){
        len++;
        p = p->next;
    }
    p = head;
    while(1){
        if((t==((len-1)/2))&&(len%2!=0)){
            return p;
        }
        if((t==(len/2))&&(len%2==0)){
            return p;
        }
        p = p->next;
        t++;
    }
}
           

結果：

二、快慢指針

通過分析發現，第一次周遊幾乎沒做什麼事，就是統計了一下連結清單的長度，當連結清單長度很長時，就會浪費大量的時間。

采用快慢指針，快指針一次走兩步，慢指針一次走一步，這樣當快指針走到連結清單結尾時，慢指針正好指向中間節點。

1. len = 2n

Eg. len = 4

第一步（初始狀态）

快慢指針都指向第一個節點（頭節點）

第二步

快指針前進兩步，慢指針前進一步

第三步

快指針到達連結清單末尾，此時慢指針正好指向題目要求的偶數個數的第二個中間節點，結束循環，

結束條件： fast == NULL

2. len = 2n+1

Eg. len = 5

第一步 （初始狀态）

第二步

快指針前進兩步，慢指針前進一步

第三步

雖然此時快指針沒有到達連結清單結尾，但是此時慢指針已經到達了連結清單中間，此時應該标記為結束标志結束循環，否則快指針去找NULL的next就會出錯

判斷條件: fast->next == NULL

是以可以得到兩種情況下的結束條件是 fast && fast->next

struct ListNode* middleNode(struct ListNode* head){
    struct ListNode *p_fast = head, *p_slow = head;
    while(p_fast && p_fast->next){
        p_fast = p_fast->next->next;
        p_slow = p_slow->next;
    }
    return p_slow;
}