#876. Middle of the Linked List

題目描述

給你一個單向鏈結串列的起點head，回傳中間的節點。

如果中間有兩個節點，回傳第二個節點。

限制條件

節點的數量為[1, 100]。
1 <= 節點值 <= 100

解題思路

Intuition

最直覺的方式，就是先取得全部的節點數量，除以2之後就是中間節點的位置，然後再重新碰到連結串列的位置就可以了。

public class Solution {
    public ListNode MiddleNode(ListNode head) {
        int count=0;
		var countNode = head;
		while(countNode!=null){
			countNode = countNode.next;
			count++;
		}
		int mid = count/2;
		for(int i=0;i<mid;i++){
			head = head.next;
		}
		return head;
    }
}

複雜度分析：

時間複雜度：總共會經過3/2n的節點，因此時間複雜度為O(n)。
空間複雜度：空間複雜度為O(1)。

Improve Intuitive Solution

如果要降低查詢的時間的話，可以用空間換時間的方式，利用Hash Table把節點位置記下來，就可以直接回傳中間值了。

public class Solution {
    public ListNode MiddleNode(ListNode head) {
        var ht = new Hashtable();
        int count=0;
		var countNode = head;
		while(countNode!=null){
            ht.Add(count,countNode);
			countNode = countNode.next;
			count++;
		}
		int mid = count/2;		
		return (ListNode)ht[mid];
    }
}

複雜度分析：

時間複雜度：雖然有Hash Table幫忙減少了重新到達中間節點那一半的時間，但是時間複雜度仍然算O(n)。
空間複雜度：空間上由於會記錄到全部的節點，因此時間複雜度會是O(n)。

Two Pointers

最好的方式是使用雙指標(Two Pointers)，建立快慢節點，快節點的前進速度是慢節點的兩倍，當快節點到達尾端的時候，慢節點就會剛好落在中間的位置。

舉例來說，假設節點數量是10，快慢節點同時從1出發，當慢節點走到2的時候，快節點會是3，依序下去會是(慢,快)：(1,1)->(2,3)->(3,5)->(4,7)->(5,9)->(6,11)，當快節點走到底時，慢節點正好是中間節點的第二個位置，也就是我們要的答案。

public class Solution {
    public ListNode MiddleNode(ListNode head) {
        if(head==null) return head;
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null && fast.next !=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

複雜度分析：

時間複雜度：實際上只花了一半的時間，但是時間複雜度還是要算O(n)，但比起前兩個解法所花的時間O((3/2)*n)、O(n)來說，還是快了一些。
空間複雜度：而空間複雜度上就比使用Hash Table還要來的少，空間複雜度為O(1)。

學習重點

雙指標