🐨1.題目

給你單鏈表的頭結(jié)點head，請你找出并返回鏈表的中間結(jié)點。
如果有兩個中間結(jié)點，則返回第二個中間結(jié)點。

示例1：

輸入： head = [1,2,3,4,5]
輸出： [3,4,5]
解釋： 鏈表只有一個中間結(jié)點，值為 3 。

示例2：

輸入： head = [1,2,3,4,5,6]
輸出： [4,5,6]
解釋： 該鏈表有兩個中間結(jié)點，值分別為 3 和 4 ，返回第二個結(jié)點。

提示：

• 鏈表的結(jié)點數(shù)范圍是 [1, 100]
• 1 <= Node.val <= 100

🐇2. 解法1-兩次遍歷

🍀2.1 思路

該題沒有對時間復(fù)雜度和空間復(fù)雜度作出要求，那么最直接的思路就是將鏈表遍歷2遍：

• 第一次遍歷：統(tǒng)計鏈表元素個數(shù)n。
• 第二次遍歷：遍歷到n/2個元素(鏈表首節(jié)點為第0個元素)。

🍀2.2 代碼實現(xiàn)

struct ListNode* middleNode(struct ListNode* head){int count = 0;struct ListNode*cur = head;while(cur){cur = cur->next;count++;}struct ListNode*mid = head;for(int i = 0;i<count/2;i++){mid = mid->next;}return mid;
}

🐁3. 解法2-快慢指針

🌾3.1 思路

既然是找中間節(jié)點，那么不妨設(shè)置兩個指針：

• 一個快指針fast，每次走2步；
• 一個慢指針slow，每次走1步。

那么當(dāng)快指針走完的時候，慢指針正好是走到中間元素

如圖所示：
我們這里需要判斷結(jié)束的條件是當(dāng)fast == NULL或者fast->next == NULL

🌾3.2 代碼實現(xiàn)

struct ListNode* middleNode(struct ListNode* head){struct ListNode*fast = head;struct ListNode*slow = head;//這里要先判斷fast，再判斷fast->next，順序不可寫反while(fast&&fast->next){slow = slow->next;fast = fast->next->next;}return slow;
}

🐮4. 題目鏈接

leetcode – 876.鏈表的中間節(jié)點