鏈表的中間結點
- 題目
- 分析
- 解題：快慢指標法 0ms 35.7MB
題目
給定一個頭結點為 head 的非空單鏈表，回傳鏈表的中間結點，
如果有兩個中間結點，則回傳第二個中間結點，
示例 1：
輸入：[1,2,3,4,5]
輸出：此串列中的結點 3 (序列化形式：[3,4,5])
回傳的結點值為 3 ， (測評系統對該結點序列化表述是 [3,4,5])，
注意，我們回傳了一個 ListNode 型別的物件 ans，這樣：
ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.
示例 2：
輸入：[1,2,3,4,5,6]
輸出：此串列中的結點 4 (序列化形式：[4,5,6])
由于該串列有兩個中間結點，值分別為 3 和 4，我們回傳第二個結點，
提示：給定鏈表的結點數介于 1 和 100 之間，
分析
找到中間節點，最經典的解法就是使用快慢指標，
快指標每次走兩個節點，慢指標每次走一個節點；當快指標走到尾節點，慢指標正好走到一半，即中間節點，
解題：快慢指標法 0ms 35.7MB
public ListNode middleNode(ListNode head) {
if (head == null || head.next == null) return head;
ListNode slow = head;
ListNode quick = head;
while (quick != null && quick.next != null) {
slow = slow.next;
quick = quick.next.next;
}
return slow;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/238630.html
標籤：其他
上一篇：輪流取石頭游戲