每日算法打卡-20200323-快慢指針法

1.題目描述

給定一個帶有頭結點 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 之間。

2.思路

方法一：數組

思路和算法

鏈表的缺點在於不能通過下標訪問對應的元素。因此我們可以考慮對鏈表進行遍歷，同時將遍歷到的元素依次放入數組 A 中。如果我們遍歷到了 N 個元素，那麼鏈表以及數組的長度也為 N，對應的中間節點即為 A[N/2]

<code>class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode[] A = new ListNode[100];
        int t = 0;
        while (head != null) {
            A[t++] = head;
            head = head.next;
        }
        return A[t / 2];
    }
}/<code>

複雜度分析

時間複雜度：O(N)O(N)，其中 NN 是給定鏈表中的結點數目。

空間複雜度：O(N)O(N)，即數組 A 用去的空間。

方法二：單指針法

我們可以對方法一進行空間優化，省去數組 A。

我們可以對鏈表進行兩次遍歷。第一次遍歷時，我們統計鏈表中的元素個數 N；第二次遍歷時，我們遍歷到第 N/2 個元素（鏈表的首節點為第 0 個元素）時，將該元素返回即可

<code>class Solution {
    public ListNode middleNode(ListNode head) {
        int n = 0;
        ListNode cur = head;
        while (cur != null) {
            ++n;
            cur = cur.next;
        }
        int k = 0;
        cur = head;
        while (k < n / 2) {
            ++k;
            cur = cur.next;
        }
        return cur;
    }
}/<code>

複雜度分析

時間複雜度：O(N)O(N)，其中 NN 是給定鏈表的結點數目。

空間複雜度：O(1)O(1)，只需要常數空間存放變量和指針。

方法三：快慢指針法

思路和算法

我們可以繼續優化方法二，用兩個指針 slow 與 fast 一起遍歷鏈表。slow 一次走一步，fast 一次走兩步。那麼當 fast 到達鏈表的末尾時，slow 必然位於中間。

<code>class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head, fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}/<code>

複雜度分析

時間複雜度：O(N)O(N)，其中 NN 是給定鏈表的結點數目。

空間複雜度：O(1)O(1)，只需要常數空間存放 slow 和 fast 兩個指針。

作者：LeetCode-Solution

閱讀更多 每日學編程 的文章

關鍵字: 指針 快慢 算法