求連結清單中間結點
-
-
- 題目描述
- 解題思路
- 實作代碼
-
題目描述
給定一個頭結點為 head 的非空單連結清單，傳回連結清單的中間結點。
如果有兩個中間結點，則傳回第二個中間結點。
該題的意思是：假定連結清單長度為len，無論連結清單長度為奇數還是偶數，傳回
len/2+1
位置的結點。
給大家兩個示例，通過示例再了解下本題：
示例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，我們傳回第二個結點。
來源：力扣（LeetCode）
連結：連結清單的中間結點
解題思路
對于該題，有兩種思路去考慮：
（1）第一種：大衆思想，先求連結清單的長度len，得到連結清單長度後，建立一個引用cur指向連結清單表頭，通過while循環，讓cur向後周遊，直到走到中間結點的位置退出循環，循環退出，此時傳回cur，cur指向的結點即為所求的連結清單中間結點。
（2）第二種：快慢指針，不知道大家對快慢指針是否有概念，這個玩意兒怕是來自國小數學哈哈哈，反正跟跑步問題相關。我們通過定義快指針
fast
和慢指針
slow
，通過while循環，當fast不為null（連結清單總結點為偶數情況）以及fast.next不為null（連結清單總結點數為奇數情況）時，讓fast與slow向後走，fast一次走兩步，slow一次走一步，fast為null以及fast.next為null時退出循環，此時slow指向的結點即為所求的連結清單中間結點。
實作代碼
public ListNode middleNode(ListNode head) {
第1種方法：求連結清單長度，尋找中間結點
//養成好習慣，先來一手判空，雖然該題說了連結清單非空哈哈哈
if(head == null){
return null;
}
//求取連結清單長度，定義cur指向表頭
int len= 1;ListNode cur = head;
while(cur.next != null){
cur = cur.next;
len++;
}
int length = 1;cur = head;
//count/2+1為連結清單中間結點位置
while(length != count/2+1){
cur = cur.next;
length++;
}
return cur;
}
public ListNode middleNode(ListNode head) {
第2種方法：快慢指針搞定它!
//首先判空
if(head == null){
return null;
}
ListNode fast = head; //讓fast與slow都指向表頭
ListNode slow = head;
while(fast != null &&fast.next != null){
fast = fast.next.next; //fast一次走兩步
slow = slow.next; //slow一次走一步
}
return slow;
}
運作結果
我們可以發現兩種方法運作時所占記憶體大小不一，但時間複雜度是一緻的。