文章目錄
- 題目描述
- 思路
- 代碼實作
- 題目附加條件
- 思路
- 代碼實作
題目描述
給定一個頭結點為 head 的非空單鏈表，回傳鏈表的中間結點，
如果有兩個中間結點，則回傳第二個中間結點，（題目來源）
思路
因為這道題目并沒有時間復雜度的規定，所以若想要解決這道問題是非常簡單的，我們只需要先遍歷一遍鏈表，統計鏈表當中的結點個數，然后再遍歷一遍鏈表，尋找中間位置的結點即可，
代碼實作
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* cur = head;//記錄當前結點位置
int count = 0;//記錄鏈表中結點的總數
while (cur)//遍歷的停止條件
{
count++;//總數加一
cur = cur->next;//指標后移
}
int mid = count / 2;//中間結點與第一個結點之間相差的結點數
struct ListNode* midnode = head;//記錄中間結點的位置
while (mid--)//從第一個結點開始，指標后移mid個結點
{
midnode = midnode->next;//指標后移
}
return midnode;//回傳中間結點
}
題目附加條件
我們可以明顯知道，上面這種思路的時間復雜度是O(n2)，那么我們有沒有辦法在只遍歷一遍鏈表的情況下找到中間結點的位置呢？也就是要求代碼的時間復雜度為O(n)，
思路
既然我們要找的是中間位置的結點，那么我們可以定義兩個指標，第一個指標指向當前遍歷到的最后一個結點，第二個指標時刻指向已經遍歷過的結點的中間結點，如此進行下去，因為第二個指標始終指向的是已經遍歷過的結點的中間結點，所以當鏈表遍歷完后直接回傳第二個指標即可，這就是所謂的“快慢指標”，
尋找規律：
我們不妨定義兩個指標名叫：fast，slow，
fast：記錄當前遍歷到的最后一個結點，（快指標）
slow：記錄已經遍歷過的結點的中間結點，（慢指標）
通過觀察，我們可以發現，當slow指標走一步時，fast指標走一步或是走兩步都滿足slow指標指向的是已經遍歷過的結點的中間結點，也就是slow指標走一步，fast指標最多可以走兩步，
所以，我們可以遍歷鏈表，當fast指標遍歷到鏈表末尾時，就立刻回傳此時的slow指標即可，
需要注意的是：因為fast指標一次是走兩步，所以當fast指標指向的內容為空或是fast指標指向的結點所指向的內容為空時，均停止遍歷鏈表，
這兩種情況下均停止遍歷，立刻回傳slow指標，
這樣，我們就在只遍歷了一遍鏈表的情況下找到了中間結點的位置，即時間復雜度為O(n)，
代碼實作
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* fast = head;//快指標
struct ListNode* slow = head;//慢指標
while (fast&&fast->next)//遍歷繼續的條件
{
slow = slow->next;//慢指標一次走一步
fast = fast->next->next;//快指標一次走兩步
}
return slow;//回傳慢指標
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/275835.html
標籤：其他