在數據結構的面試中，經常會出現這樣的問題：如何快速找到未知長度單鏈表的中間節點？通常，面試官會期待你提供兩種解法：一種是最基本的普通方法，另一種是更高效的 advanced 方法。本文將詳細介紹這兩種方法。

普通方法

思路
普通方法首先需要遍歷整個鏈表以確定其長度 L。然后，再次從頭節點出發，循環 L/2 次找到中間節點。

算法步驟

1. 初始化一個變量 length 用于記錄鏈表長度，將頭節點 head 賦值給 length。
2. 創建一個臨時節點 temp，用于遍歷鏈表，將頭節點賦值給 temp。
3. 遍歷鏈表，每遍歷一次，length 減一，直到 length 等于 0。
4. 將 temp 重新賦值為頭節點 head，循環 length/2 次，每次移動 temp 一步。
5. 當循環結束時，temp 所指向的節點即為鏈表的中間節點。

時間復雜度
普通方法的時間復雜度為 O(L + L/2) = O(3L/2)，其中 L 為鏈表的長度。

代碼實現

struct ListNode {int val;struct ListNode* next;
};struct ListNode* findMiddleNode(struct ListNode* head) {int length = 0;struct ListNode* temp = head;while (temp != NULL) {length++;temp = temp->next;}temp = head;for (int i = 0; i < length / 2; i++) {temp = temp->next;}return temp;
}

高級方法

思路
高級方法使用快慢指針。快指針每次移動兩步，慢指針每次移動一步。當快指針到達鏈表末尾時，慢指針所指的節點就是鏈表的中間節點。

算法步驟

1. 初始化兩個指針，快指針 fast 和慢指針 slow，都指向頭節點 head。
2. 讓快指針先移動，每次移動兩步；慢指針移動一步。
3. 當快指針到達鏈表的末尾時，慢指針所指向的節點就是鏈表的中間節點。

時間復雜度
高級方法的時間復雜度為 O(L)，其中 L 為鏈表的長度。

代碼實現

struct ListNode {int val;struct ListNode* next;
};
struct ListNode* findMiddleNode(struct ListNode* head) {struct ListNode *slow = head, *fast = head;while (fast != NULL && fast->next != NULL) {slow = slow->next;fast = fast->next->next;}return slow;
}

總結

本文介紹了在未知長度的單鏈表中快速找到中間節點的兩種方法：普通方法和高級方法。普通方法雖然簡單易懂，但其時間復雜度較高。相比之下，高級方法利用快慢指針，將時間復雜度降低到了 O(L)，更為高效。在實際面試中，掌握這兩種方法將對您解決鏈表問題大有裨益。