# Leetcode [No. 876] Middle of the Linked List(EASY)

## 題目

https://leetcode.com/problems/middle-of-the-linked-list/description/

## 思路

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        unordered_map<int, ListNode*> hashMap;
        ListNode* cur = head;
        int node_cnt = 0;
        while(cur != nullptr)
        {
            hashMap[node_cnt] = cur;
            cur = cur->next;
            node_cnt++;    
        }
        // cout << "node_cnt = " << node_cnt << endl;
        return hashMap[node_cnt/2];
    }
};

### 解法分析
+ time complexity: O(n)

### 執行結果

## 加速:

+ 不使用hashMap紀錄，省空間省時間

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* cur = head;
        int node_cnt = 0;
        while(cur != nullptr)
        {
            cur = cur->next;
            node_cnt++;    
        }
        cur = head;
        int cnt = 0;
        while(cnt < node_cnt/2)
        {
            cur = cur->next;
            cnt++;
        }
        // cout << "node_cnt = " << node_cnt << endl;
        return cur;
    }
};

### 解法分析
+ time complexity: O(n)

### 執行結果


## 改良

+ 使用快慢指標就可以處理

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

        while(fast != nullptr && fast->next != nullptr)
        {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

### 解法分析
+ time complexity: O(n)

### 執行結果