題目： LeetCode - 876. Middle of the Linked List

題目說明

給一個 Linked List，找到 List 中間的那個 node。

解題思路

  • 解法一：先遍歷一遍，得到整個 List 的長度，然後在用一個 node 走到長度的一半即可。

  • 解法二：使用 Floyd Cycle Detection Algorithm 的概念，當 hare 走到結尾時，tortoise 剛好會走到一半。

參考解法

解法一：

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        int length = 0;
        auto ans = head;
        for(auto it = head; it != nullptr; it = it->next, ++length);
        for(int i = 0; i < length / 2; ++i, ans = ans->next);
        return ans;
    }
};

解法二：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        auto tortoise = head, hare = head;
        while(hare && hare->next)
        {
            hare = hare->next->next;
            tortoise = tortoise->next;
        }
        return tortoise;
    }
};