文章目錄
- 題目要求
- 方法1：統計長度 走兩遍
- 方法2：快慢指標
題目要求
鏈接：876. 鏈表的中間結點 - 力扣（LeetCode） (leetcode-cn.com)
方法1：統計長度 走兩遍
思路：
-
第一步：從頭遍歷一遍鏈表得出鏈表的長度，記為size
-
第二步:從頭開始走，走 mid = size/2步 就是鏈表的中間結點
whle( mid--) ==>這樣是回圈mid次 while(--mid) ==>這樣是回圈mid-1次 -
無論是奇數個結點還是偶數個結點都合適
圖解
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
//從頭開始統計鏈表長度
struct ListNode* cur = head;
int size = 0;
while(cur)
{
size++;
cur = cur->next;
}
//從頭開始重新遍歷，走長度的一半步
cur = head;
int mid = size /2;
//走mid步
while(mid--)
{
cur = cur->next;
}
//走完mid步，cur指向的就是中間結點
return cur;
}
方法2：快慢指標
思路
-
定義兩個指標，一個fast 一個slow
-
二者從頭開始遍歷 fast走兩步 slow走一步
- fast = fast -> next -> next
- slow = slow ->next
-
奇數個結點結束條件：fast 走到尾結點 (fast ->next NULL)
- 偶數個結點結束條件：fast走到空 (fast == NULL)
因為不知道結點個數是奇數個還是偶數個
所以回圈條件可寫成
while(fast && fast ->next )
當fast走到NULL 或者 fast->next為空時，&&發生短路，跳出回圈
//不可寫成 while(fast->next && fast) 可能存在對空指標解參考情況
struct ListNode* middleNode(struct ListNode* head)
{
//定義快慢指標
struct ListNode* fast = head;
struct ListNode* slow = head;
while(fast && fast->next)
{
//快指標走兩步
fast = fast->next->next;
//慢指標走一步
slow = slow ->next;
}
return slow;
}
易錯點：while判斷中： fast->next 和fast 順序
//err
while(fast->next && fast)
{
//快指標走兩步
fast = fast->next->next;
//慢指標走一步
slow = slow ->next;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/394091.html
標籤：其他