Linked List的題目相對單純一點，大概就一個技巧就是Two Pointer，因為我們只能單向的尋訪鏈結串列，所以時間複雜度通常都是O(n)。

Linked List有幾個地方要注意的是，如果不小心斷了鏈接然後沒有去記錄到下一個節點的位置的話，我們就永遠找不到囉。

例題1-Reverse Linked List

1. Brute Force: 這一題最簡單的方式就是我們用一個Array，有順序性的從頭到尾把節點存起來，然後在從後面遍歷Array把節點都串起來。這樣的時間複雜度是O(n)，空間複雜度也是O(n)。

2. 我們拿一個中間的節點來想要怎麼操作(假設我們node1之前已經reverse完了)。
   

一開始我們先看看兩個指標分別是cur跟pre，cur就是我現在要reverse的節點，pre就是我前一個節點，也就是我reverse後cur要指向的節點。

首先我勢必要把cur的next指向pre，但是這邊要記得，如果我指向的話，node3就找不到了，所以我們有一個tmp指標去保存node3的位置，這樣我們就完成reverse而且還記錄了被斷開的節點，接下來我們在更新cur, pre 跟 tmp節點，我們的停止條件就是cur指標指到最後的Node那就代表我們reverse完了。

接著我們再回來思考第一個節點要怎麼實作這個reverse呢？我們第一個節點reverse完就變成就後一個了，也就是要指向Node，所以我們一開始讓pre是Node就可以囉！

最後我們要回傳Link List的頭，所以我們可以發現，這個頭剛好就是pre指標。

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        pre = None
        cur = head
        
        while cur:
            
            tmp = cur.next
            cur.next = pre
            
            pre = cur
            cur = tmp
            
        return pre

例題2-Remove Nth Node From End of List

這一題要我們移除倒數第K個節點，所以我們要做的事情有兩個，首先我們要先找到倒數第K個節點，接著我們要移除他，我相信移除不會是太難的問題，重點會在「怎麼找到倒數第K個節點」。

1. 最直觀的方式就是，我們先遍歷過這個LinkedList一遍，存在Array裡面，這樣就可以知道倒數第K個節點是哪個了，然後我們在遍歷第二次以後，就可以移除他。

2. 這邊其實我們可以利用Two Pointer的方法，只需要遍歷一遍Linked List就可以知道倒數第K個節點囉。首先我們有兩個指針分別是slow及fast指針，一開始都指向head，接著我fast往前移K次
   

然後fast跟slow再一起移動，直到fast到Node，我們就會發現，slow就會指向倒數第K個節點囉。

程式碼裡面大家可以看到，我在head之前又新增一個空的節點，其實理由很簡單，因為我找到我要移除的那個節點後，我要把它前一個節點指向他後一個節點，大家記得嗎？因為我Linked List只能單方向移動，所以我在head之前建立一個空節點，跟著大家一起移動到停止的時候，那他就會在倒數第K個節點的前面位置啦~

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        
        fast = None
        slow = None
        dummy_head = ListNode(0)
        dummy_head.next = head
        tmp = dummy_head
        if head:
            slow = head
            fast = head    
        for _ in range(n):
            fast = fast.next
        while fast:
            slow = slow.next
            fast = fast.next
            tmp = tmp.next
        tmp.next = slow.next
        return dummy_head.next

例題3-Linked List Cycle

接著我們來看案這一題，題目要求我們知道這個Linked List有沒有圓圈。

1. Brute Force: 其實最簡單的方式就是我們用一個Set紀錄我們走過的地方，那當我發現我現在這個Node如果再set裡就代表這裡有圈圈了。
   但是這樣的空間複雜度是O(n)，有沒有更好的方法呢？

2. 其實是有的而且這是一個很有趣的演算法，它叫Floyd's Algorithm，中文叫龜兔賽跑演算法。概念是這樣的，我兔子一次走兩步，烏龜一次走一步，如果兔子跟烏龜有同時到同一個節點那就代表一定有圈圈，因為沒有圓圈的話兔子會先走完，也就是走到None，反之就是有圓圈囉。

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        
        if not head or not head.next:
            return False
        turtle = head
        hare = head.next

        while hare and hare.next:
            if hare == turtle:
                return True
            else:
                hare = hare.next.next
                turtle = turtle.next
        return False