# 876. Middle of the Linked List
###### tags: `Python`,`Leetcode`
https://leetcode.com/problems/middle-of-the-linked-list/
## MyCode!
### Way 1
### Way 2

## 解題思路
### Way 1
* 題目要求輸出 middle node，但 Linked List 須逐步指到下一個 node，無法使用 index 取出
* 設計龜兔賽跑的方式:
1. 第一顆 Fast，速度是第二顆 Slow 的兩倍。當 Fast 走到 Linked List 的尾巴， Slow 應該走到 List 中間
2. 最後 return Slow，後面的料就會跟著扯出來
3. 當 Fast 或是 Fast.next 還有東西可以走，就要走完
### Way 2
* 一開始就把第一顆 node 丟進可用 index 存取的 List 中
* 不斷使用 List 最後一顆 node 去叫出下一顆，把下一顆的貼進 List 中(循環循環到叫不出下一顆)
* 把 List 的 len()//2 位置之 node return 出來

## 解法
### Way 1
#### Step 1 : 龜兔賽跑從頭開始，全域變數 Fast = Slow = Head
#### Step 2 : 當 Fast != Null and Fast.next != Null 時不斷龜跑兔跑
* **While 迴圈的條件設置原因 ?**
1. 因為 Fast 最後一顆要走完或是走到最後一顆的下一顆 Null Node， return 才會是 middle(或第二顆 middle)
2. 如果沒有 Fast.next 這條件，只有 Fast。Loop 跑到最後一顆 node 前就會停下， Fast.next 是 NoneType ，Fast.next.next 不成立
3. 如果沒有 Fast 這條件，只有 Fast.next 。Loop 無法跑出來，因為 Fast 是 NoneType，Fast.next 不成立
* **第一顆 Fast，速度是第二顆 Slow 的兩倍**
1. Fast 兩顆兩顆跳
2. Slow 一顆一顆跳
#### Step 3 : Return 龜的 node

### Way 2
#### Step 1：開始就把第一顆 node 丟進可用 index 存取的 List 中
#### Step 2 : 當只要有下一顆存在，就要跑下去
* 不斷使用 List 最後一顆 node 去叫出下一顆，把下一顆的貼進 List 中(循環循環到叫不出下一顆)

#### Step 3 :　把 List 的 len()//2 位置之 node return 出來