本系列博文為leetcode-explore-learn子欄目學習筆記，如有不詳之處，請參考leetcode官網：https://leetcode-cn.com/explore/learn/card/linked-list/

所有例題的編程語言為python

1.反轉一個鏈表

leetcode 206
思路1： 迭代求解，將當前結點next信息保存下來，然后將前一個節點的信息存入當前結點的next中。更新當前結點。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution(object):def reverseList(self, head):""":type head: ListNode:rtype: ListNode"""if head==None:return headpre_node=Nonecur_node=headwhile(cur_node):next_node=cur_node.nextcur_node.next=pre_nodepre_node=cur_nodecur_node=next_nodereturn pre_node   

思路2：
遞歸：假設鏈表的其余部分都已經被翻轉，現在該如何翻轉它前面的部分。由最后一個開始往前不斷翻轉

class Solution(object):def reverseList(self, head):""":type head: ListNode:rtype: ListNode"""if head==None or head.next==None:return headp=self.reverseList(head.next)   # 記錄最后一個結點作為頭指針用的。head.next.next=headhead.next=Nonereturn p

2.移除鏈表元素

刪除鏈表中等于給定值 val 的所有節點。
思路：遍歷鏈表的每一結點，如果值等于給定值將其刪除即可。
注意點：要刪除鏈表節點時，可以使用啞結點技巧，防止刪原鏈表的頭結點。最后返回時，返回dummy.next即可。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution(object):def removeElements(self, head, val):""":type head: ListNode:type val: int:rtype: ListNode"""dummy=ListNode(0)dummy.next=headpre_node=dummycur_node=dummy.nextwhile(cur_node):next_node=cur_node.nextif cur_node.val==val:pre_node.next=next_node  # 刪除結點else:pre_node=cur_nodecur_node=next_nodereturn dummy.next

3.奇偶鏈表

給定一個單鏈表，把所有奇數節點和偶數節點（節點 編號的奇偶性）分別排在一起。
思路1：原來的鏈表分成奇偶兩個子鏈表，然后將偶鏈表鏈接到奇鏈表后面。
沒有使用額外的空間，直接從原來的鏈表中截取。

# Definition for singly-linked list.
class ListNode(object):def __init__(self, x):self.val = xself.next = Noneclass Solution(object):def oddEvenList(self, head):""":type head: ListNode:rtype: ListNode"""if head==None:return headeven_h=ListNode(0)even_node=even_hcur_node=headi=1while(cur_node):next_node=cur_node.nextif i %2==0:cur_node.next=None   # 將node.next的值給設置為零，能防止成環even_node.next=cur_nodeeven_node=even_node.nextpre_node.next=next_nodeelse:pre_node=cur_nodecur_node=next_nodei+=1cur_node=head.nextpre_node=headwhile(cur_node):print(pre_node.val)pre_node=cur_nodecur_node=cur_node.nextpre_node.next=even_h.nextreturn head        

4.回文鏈表

判斷一個鏈表是否為回文鏈表。
o(n)時間復雜度，o(1)空間復雜度

思路1：可以先把鏈表裝進數組中，判斷數組中元素是否構成回文。數組的前后遍歷比單鏈表方便。時間復雜度o(n)，空間復雜度o(n)

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = Noneclass Solution(object):def isPalindrome(self, head):""":type head: ListNode:rtype: bool"""if not head or not head.next:return Truelst=[]p=headwhile(p):lst.append(p.val)p=p.nextreturn lst==lst[::-1]

思路2：翻轉原鏈表，對照兩個鏈表是否一致，如果回文鏈表應該是一致的，反之原鏈表不為回文鏈表。時間復雜度o(n),空間復雜度o(n)

# Definition for singly-linked list.
class ListNode(object):def __init__(self, x):self.val = xself.next = Noneclass Solution(object):def isPalindrome(self, head):""":type head: ListNode:rtype: bool"""if head==None or head.next==None:return True# 備份原鏈表head_be=ListNode(0)node=headnode_be=head_be    while(node):node_be.next=ListNode(node.val)node_be=node_be.nextnode=node.next# 轉置原鏈表pre_node=Nonecur_node=headwhile(cur_node):next_node=cur_node.nextcur_node.next=pre_nodepre_node=cur_nodecur_node=next_node# 比較兩個鏈表node_be=head_be.nextnode_af=pre_nodewhile(node_be and node_af):if node_be.val!=node_af.val:return Falsenode_be=node_be.nextnode_af=node_af.nextreturn True

思路三：避免使用 O(n)O(n) 額外空間的方法就是改變輸入。

我們可以將鏈表的后半部分反轉（修改鏈表結構），然后將前半部分和后半部分進行比較。比較完成后我們應該將鏈表恢復原樣。雖然不需要恢復也能通過測試用例，因為使用該函數的人不希望鏈表結構被更改。

class Solution(object):def isPalindrome(self, head):""":type head: ListNode:rtype: bool"""if not head or not head.next:return True# 計算鏈表長度p1=headn=1while(p1.next):p1=p1.nextn+=1p1=headp2=headif n==2:if  head.val==head.next.val:return Trueelse:return False# 找鏈表中點for i in range(int(round(n/2.0))-1): # 0p1=p1.nexthalf_end=p1     # 前一半鏈表的最后一個節點# 翻轉后一半鏈表p1=p1.nextpre_node=Nonefor i in range(int(n/2.0)): # 0,1next_node=p1.nextp1.next=pre_nodepre_node=p1p1=next_nodehalf_end.next=pre_nodep1=head# 比較前一半和翻轉后的后一半。for i in range(int(round(n/2.0))): # 0,1p1=p1.nextfor i in range(int(n/2)):# 0,1if p1.val!=p2.val:return Falsep1=p1.nextp2=p2.nextreturn True

5.小結

1.使用鏈表時不易調試，自己多嘗試幾個測試用例總是很有用的，通過輸出鏈表節點的值來觀測代碼運行情況。

2.多指針時，為指針設定合適的名稱，防止自己被搞混

3.單鏈表操作時，儲存前一個節點的信息往往是有效的。