Linked List 基本原理
===
在介紹 Linked List 之前要先了解陣列(Array)、動態陣列與[指標(Pointer)](https://hackmd.io/@yoch/S106tl53d)。

在 C 語言中簡單陣列宣告如下，直接告知電腦我們需要多大的記憶體空間。

int arr[5];

int arr[5] = {1,2,3,4,5};

如要自行配置與刪除記憶體空間，可以使用 `new` 與 `delete` ，以下為動態方式配置一個 int 型態大小的記憶體空間與 100 個 int 大小的記憶體空間與刪除。

int *p = new int;

int *p = new int(100);

delete[] p;

## Linked List / Array
陣列與 Linked List 最大不同在於陣列存放了數值不易移動，以下面例子當要在 3 的後面存放 8 時，就得重新再跟電腦索取大一點的空間，並將 4 與 5 元素往後移動。

int arr[5];
for(int i = 0; i < 5; i++)
{
    arr[i] = i + 1;
}

// 放入 8
int newArr[6];
for(int i = 0; i < 6; i++)
{
    if(i == 3)
    {
        newArr[i] = 8;
        continue;
    }
    newArr[i] = arr[i];
}


對 Linked List 來說增加或減少都非常方便，其好處是彈性靈活，能動態與記憶體要空間或釋放空間。


那有在寫 LeetCode 應該都很常看到 Linked List 題型，也很常看到各路高手們這樣使用 ↓

// 19. Remove Nth Node From End of List
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *fast = head, *slow = head;
        for (int i = 0; i < n; i++) fast = fast->next;
        if (!fast) return head->next;
        while (fast->next) fast = fast->next, slow = slow->next;
        slow->next = slow->next->next;
        return head;
    }
};

那麼會好奇為何可以透過 fast 與 slow 來得到 head 的結果呢?! 這就牽扯到指標啦~ 一開始讓 fast 與 slow 變數都獲得了 head 的位址。


那我們將 function 參數 ListNode 為 1→2→3→4→5→null 而 n 設為 2，可以直接看到第 9 行 `slow->next = slow->next->next` 這意思如下圖所示，原本 while 迴圈讓 slow 指到 4 這個位址時的下一步是 next->next 所以就直接跳過 5。


可以看到 head 永遠都是在該 linked list 的頭，因此不會有 ListNode null 的問題，由於 fast 與 slow 與 head 共用相同位址，而 slow 將 4 跳過就表示指到 3 位址的下一個位址為 5，新的 ListNode 就變為 1→2→3→5→null 囉。


## 參考
>Linked List: Intro(簡介)：http://alrightchiu.github.io/SecondRound/linked-list-introjian-jie.html
>[資料結構] Linked List：https://hackmd.io/@Zero871015/H12vTu8aX?type=view
>C 語言：鏈結串列(Linked List)的建立與刪除：https://kopu.chat/2017/06/02/c-%E8%AA%9E%E8%A8%80%EF%BC%9A%E9%8F%88%E7%B5%90%E4%B8%B2%E5%88%97linked-list%E7%9A%84%E5%BB%BA%E7%AB%8B%E8%88%87%E5%88%AA%E9%99%A4/