---
# System prepended metadata

title: 876. Middle of the Linked List
tags: [Leetcode, Python]

---

# 876. Middle of the Linked List
###### tags: `Python`,`Leetcode`
https://leetcode.com/problems/middle-of-the-linked-list/
## MyCode!
### Way 1
![](https://i.imgur.com/nswW3xG.png)
### Way 2
![](https://i.imgur.com/6pWELdM.png)

## 解題思路
### 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 出來