主題
題目連結：
題目意譯：
請實作你自己的連結串列（Linked List）。你可以選擇使用一個單向或是雙向的連結串列。
一個單向連結串列裡一個節點應有著兩個屬性：val 和 next。val 為當前節點的數值，而 next 為下一個節點的一個指標/參考。
如果你想要使用雙向連界串列，你將需要再另一個屬性 prev 來表示連結串列中的前一個節點。假設串列中所有節點的索引值從 0 開始數。
實作類別 MyLinkedList：
MyLinkedList() 初始化物件 MyLinkedList。
int get(int index) 抓取串列第 index 個節點的值。如果 index 不合法，則回傳 -1。
void addAtHead(int val) 在串列第一個元素的前面加上一個值為 val 的節點。插入後，新插入的節點將會是串列的第一個節點。
void addAtTail(int val) 在串列最後一個元素的後面加上一個值為 val 的節點。
void addAtIndex(int index, int val) 在串列第 index 個節點前面加上一個值為 val 的節點。如果 index 等於串列的長度之值，則該節點將會被插入到串列的尾端。如果 index 大於串列長度，則該節點將不會被插入。
void deleteAtIndex(int index) 刪除串列中第 index 個節點，前提是 index 是合法的。
限制：
0 ≦ index, val ≦ 1000
請勿使用內建連結串列之函式庫。
至多呼叫 get 、 addAtHead 、 addAtTail 、 addAtIndex 和 deleteAtIndex 2000 次。
範例測資：
範例 1：
Input
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
Output
[null, null, null, null, 2, null, 3]
Explanation
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2); // 連結串列變為 1->2->3
myLinkedList.get(1); // 回傳 2
myLinkedList.deleteAtIndex(1); // 現在連結串列為 1->3
myLinkedList.get(1); // 回傳 3
解題思維：
就是單純的模擬題而已。
首先，我們定義節點（這邊使用單向的節點）本身的資料結構（下稱 node）。這邊就按照題目的要求定義即可——有 val 存值，也有 next 指到下一個節點。而這就夠了。
接著，我們在 MyLinkedList 裡面定義三個 node 「指標」，分別是 dummy 、 nowAt 和 buffer。前者是作為假的頭存在，使整個串列保證有一個節點存在（會比較方便，例如插入節點的時候，如這題所提及）、中間則是用來掃過串列用的，最後則是暫時指向被刪除的節點用的。此外還需要一個變數 length，來記錄整個串列的長度（不包含 dummy，因此初始值為 0）。
接著就可以來依序處理每一個函式：
MyLinkedList()：因為是初始化用的，所以就是單純地把 length 設為 0 以及 dummy 的 next 設為空指標。
get(index)：先判斷 index 合不合法，也就是判斷 index 是否 ≧ length。如果是則不合法（不用判斷是否 < 0，題目本身已經有所限制了）；反之，則從 dummy 的 next 開始往後跑 index 個節點（用 nowAt 去掃過串列），停下來的節點之值即是應回傳之值。
addAtHead(val)：如同前面所述，現在 dummy 派上了用場。因為我們可以直接先把新的節點之 next 指向原本 dummy 的 next 之內容，然後再把 dummy 的 next 改指向新的節點。最後將 length 加 1 即可。
addAtTail(val)：這邊 dummy 也可能會派上用場，因為串列有可能為空（記得 dummy 不算數）。而有了 dummy 之後我們便可省略掉額外的判斷，即統一從 dummy 開始跑到串列的結尾然後把 dummy 的 next 指向新的節點即可。最後記得把 length 加上 1。
addAtIndex(index, val)：先類似上面的 get() 跑過 index 個節點（不過記得先判斷 index 的範圍，不能 > length），不過這次是直接從 dummy 開始算（因為我們是要插在第 index 個節點的「前面」）。nowAt 到達定位後，剩下其實就跟 addAtHead 的作法基本一致——先把新的節點之 next 指向原本 nowAt 的 next 之內容，然後再把 nowAt 的 next 改指向新的節點。最後將 length 加 1 即可。
而最後的 deleteAtIndex(index)：先學 addAtIndex 從 dummy 出發數 index 個節點（這邊也要記得先判斷 index 的範圍，不能 ≧ length），然後讓 buffer 去正式地指向第 index 個節點（因此 nowAt 實際上是在第 index - 1 個節點）。然後把 nowAt 的 next 指向 buffer 的 next 即可（也就是繞過 buffer 那個節點）並刪除 buffer 即可（不過，不去釋放記憶體空間也不會怎樣就是了。至少在本題是如此）。最後把 length 減去 1 即可大功告成。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
