最近開始重新了解資料結構，並且選擇python作為實作的語言，另外，除了實作出具體可行的結構外，也要求自己在Leetcode上練一些相關的題目，並且把一些要注意的點記錄在此。
Linked-list簡介及特點
Linked-list是由一連串的節點（Node）所構成，每個節點指向下一個節點，而最後一個節點則指向Null（在python裡面是None）。
因此，每個節點本身應該要有兩種屬性（attribute），一個是本身帶有的值或者是資料，另一個則是指向下一個節點的指標（pointer）。
我想Linked-list與一般陣列（array）比起來最大的不同點在於：
陣列使用一連串的記憶體位置，因此可以透過array[index]直接存取資料，但是相對的，若要在陣列中加入或是刪除元素，則需要大量的資料搬移。
（python中的list雖然用法跟陣列很類似，並卻不是這樣子的實作方式，我在另一篇文章中有提到。而像是在C語言中，陣列所記錄的其實是第一個元素的地址，而index就是相對於第一個元素的偏移量了，所以才是從0開始。）
而Linked-list的資料則散落在記憶體中各處，加入或是刪除元素只需要改變pointer即可完成，但是相對的，在資料的讀取上比較適合循序的使用，無法直接取得特定順序的值（比如說沒辦法直接知道list[3]）。
實作概念
我把整個linked-list的實作分成兩個類別（class），一個是包含了資料及指標兩個屬性的節點（class ListNode），另一個則是定義出各種資料結構操作的list本身（class SingleLinkedList）。
程式碼部分很多是參考自這裡，再加上一些他沒有實作的功能（像是reverse()），我的完整程式碼在這。
由於每個節點只有指向下一個結點，而沒有指出上一個結點，所以屬於single linked-list，相對於有指出上一個節點的double linked-list。
ListNode
class ListNode:
def __init__(self, data): # store data
self.data = data # store the reference (next item)
self.next = None
return
在建立一個節點時，需要傳入一個data的值，並且指標預設是指向None的。
node1 = ListNode(15)這樣就會建立一個帶有15的資料的節點了，接下來我們看看怎麼把節點放進list裡面。
Single Linked-list
class SingleLinkedList:
def __init__(self): self.head = None
self.tail = None
return
在建立list的一開始，我們預設裡面是沒有節點的。而linked-list本身帶有head跟tail兩個屬性。當我們加入一個新的節點時：
- 若list本身還沒有任何節點，則head以及tail都會變成新的結點
- 若list已經包含有其他節點，則新加入的節點變成新的tail（本來的tail指向新的節點）。
def add_list_item(self, item): # make sure item is a proper node
if not isinstance(item, ListNode):
item = ListNode(item)
if self.head is None:
self.head = item
else:
self.tail.next = item
self.tail = item
return
其中比較需要注意的是，在取得item之後，要檢查item是否是一個結點，若不是的話則使用ListNode(item)建立一個帶有item資料的節點。
list1 = SingleLinkedList()list1.add_list_item(node1)
list1.add_list_item(12)
這樣子就建立一個名為list1的linked-list，裡面包含了帶有資料15以及12的節點了。
題目練習
- Leetcode#206 Reverse Linked List（easy）：
練習的第一題是反轉一個linked-list（1->2->3變成3->2->1），主要是在反轉一個節點的指標時，必須要記住三個節點（以程式碼為例就是prev, current, head），才不會在改變指標後無法跳到本來的下一個節點，算是滿好理解的概念，寫出來的時間複雜度是O(n)。
def reverseList(self, head): prev = None
while head:
current = head
head = head.next
current.next = prev
prev = current
return prev
2. Leetcode#328 Odd Even Linked List（medium）：
這題是把一個linked-list轉換成一個新的linked-list，先把奇數項跑完後再跑偶數項，像是輸入1->2->3->4->5->6的話，就要輸出結果1->3->5->2->4->6，其中的數字代表的是節點的index而非節點帶有的數值。
我的作法是單純的做出兩個list，一個只放奇數項、一個只放偶數項，跑完後再把奇數最後一項的next指向偶數項的head，要注意一開始就要保留兩個list的head，之後才能夠這樣做操作。做出來的結果是72ms，超過90%的解，時間複雜度也是O(n)。
def oddEvenList(self, head): if head is not None:
odd_node = odd_head = head
head = head.next
else:
return None if head is not None:
even_node = even_head = head
head = head.next
else:
return odd_head count = 3
while head is not None:
if count % 2 == 1:
odd_node.next = head
odd_node = odd_node.next
else:
even_node.next = head
even_node = even_node.next
head = head.next
count = count + 1 odd_node.next = even_head
even_node.next = None
return odd_head
