注意：

• 這里的head是只存儲地址。

實例講解

prev = None  # 前指針節點
curr = head  # 當前指針節點
# 每次循環，都將當前節點指向它前面的節點，然后當前節點和前節點后移
while curr:nextTemp = curr.next  # 臨時節點，暫存當前節點的下一節點，用于后移curr.next = prev  # 將當前節點指向它前面的節點prev = curr  # 前指針后移curr = nextTemp  # 當前指針后移
return prev 

• 第四行的nextTemp = curr.next ：(.next在等號右邊)表示下一個節點的地址
• 第五行的curr.next (.next在等號左邊)表示curr所指節點的地址

1 .鏈表基本功能

class ListNode:
"""
創建單個節點
"""
def __init__(self, x):self.val = xself.next = Noneclass MyLinkedList(object):"""單鏈表"""def __init__(self):"""頭指針默認地址為空長度為0"""self.head = Noneself.length = 0def is_empty(self):"""判斷鏈表是否為空"""return self.head == Nonedef get(self, index):"""依據索引值獲取指定節點值（下表從0開始）:type index: int:rtype: int"""if index < 0 or index >= self.length:"""索引值小于0或者索引值大于等于長度，返回-1"""return -1p = self.headfor i in range(self.length):if i == index:return p.valelse:p = p.nextdef addAtHead(self, val):"""頭部添加元素"""# 先創建一個保存val值的節點node = ListNode(val)# 將新節點的鏈接域next指向頭節點，即self.head指向的位置node.next = self.head# 將鏈表的頭self.head指向新節點self.head = nodeself.length += 1def addAtTail(self, val):"""尾部添加元素"""node = ListNode(val)# 先判斷鏈表是否為空，若是空鏈表，則將self.head指向新節點if self.is_empty():self.head = node# 若不為空，則找到尾部，將尾節點的next指向新節點else:cur = self.headwhile cur.next:"""找到最后一個節點"""cur = cur.nextcur.next = nodeself.length += 1def addAtIndex(self, index, val):"""在指定為值添加索引，下標從0開始思想：新建一個計數變量count:type index: int:type val: int:rtype: None"""head = self.headif index <= 0:self.addAtHead(val)elif index == self.length:"""索引值等于鏈表長度，講節點加到鏈表的尾部"""self.addAtTail(val)elif index < self.length and index > 0:prev = headcount = 0while count < index - 1:count += 1prev = prev.nextnode = ListNode(val)node.next = prev.nextprev.next = nodeself.length += 1def deleteNode(self, val):"""刪除指定節點node ,從頭遍歷:param node::return: 返回新鏈表q"""head = self.headq = head"""p,q 用來 迭代"""p = q.nextif q.val == val:    """如果頭結點就是要刪除的結"""self.length -= 1self.head = p"""要改變self.head,因為遍歷的時候是從self.head開始的"""print('self.length:', self.length)return pwhile p:if p.val == val:q.next = p.nextself.length -= 1print('lenth', self.length)return qelse:q = pp = p.nextdef deleteAtIndex(self, index):"""在指定位置刪除:type index: int:rtype: None"""prev = self.headif index == 0:self.head = self.head.nextelif index > 0 and index < self.length:# count從1開始count = 1while count < index:prev = prev.indexprev.next = prev.next.nextself.length -= 1def travel(self):"""遍歷鏈表"""cur = self.headwhile cur:print('val:', cur.val)cur = cur.nextprint("")def midNode(self):"""快慢指針,尋找中間節點fast走兩步，slow走一步:return:返回mid的值"""head = self.headif head is None or head.next is None:"""沒有節點，或者只有一個節點"""return head.valfast = headslow = headwhile fast.next and fast.next.next:"""當為奇數個點的時候，fast.next會為空，跳出while循環當為偶數個點的時候，fast.next.next會為空，跳出while循環"""fast = fast.next.nextslow = slow.nextif fast.next:print('有偶數個點')else:print('有奇數個點')return slow.valdef reverseList(self, head):"""反轉一個單向鏈表:param head:頭部指針:param prev:反轉后的頭結點:return: 返回反轉后的鏈表"""prev = None  # 前指針節點curr = head  # 當前指針節點# 每次循環，都將當前節點指向它前面的節點，然后當前節點和前節點后移while curr:nextTemp = curr.next  # 臨時節點，暫存當前節點的下一節點，用于后移curr.next = prev  # 將當前節點指向它前面的節點prev = curr  # 前指針后移curr = nextTemp  # 當前指針后移return prev# 遞歸思路：在return處調用自己（尾遞歸）# if not head:#     return prev## curr, head.next = head.next, prev  # 新舊鏈表的兩個方向同時前進# return self.reverseList(curr, head)def isPalindrome(self):"""判斷回文鏈表的思想：1.找到中間節點slow2.把后半部分，逆序3.把前半部分和后半部分比較:type head: ListNode:rtype: bool"""head = self.headfast = headslow = headwhile fast and fast.next:"""當fast.next為None說明，fast已經在最后一個節點。也表明有奇數個點當fast.next.next為空None，fast在倒數第二個節點。也表明有偶數個點"""fast = fast.next.nextslow = slow.nextprev = None  # 前指針節點curr = slow  # 當前指針節點# 每次循環，都將當前節點指向它前面的節點，然后當前節點和前節點后移while curr:nextTemp = curr.next  # 臨時節點，暫存當前節點的下一節點，用于后移curr.next = prev  # 將當前節點指向它前面的節點prev = curr  # 前指針后移curr = nextTemp  # 當前指針后移while head and prev:if head.val != prev.val:return Falsehead = head.nextprev = prev.nextreturn Truedef getIntersectionNode(self, headA, headB):"""相交鏈表，找到兩個單鏈表相交的起始節點例如：listA = [4,1,8,4,5], listB = [5,0,1,8,4,5]相交節點的值為8:type head1, head1: ListNode:rtype: ListNode""""""定義兩個指針, 第一輪讓兩個到達末尾的節點指向另一個鏈表的頭部, 最后如果相遇則為交點(在第一輪移動中恰好抹除了長度差)兩個指針等于移動了相同的距離, 有交點就返回, 無交點就是各走了兩條指針的長度"""p = headAq = headB# 在這里第一輪體現在pA和pB第一次到達尾部會移向另一鏈表的表頭, 而第二輪體現在如果pA或pB相交就返回交點, 不相交最后就是null == nullwhile p != q:p = p.next if p else headB  # 如果p成立，p = p.next,若不成立，p = headBq = q.next if q else headAreturn pL = MyLinkedList()
print('----插入節點：-----')
L.addAtTail(1)
L.addAtTail(2)
L.addAtTail(3)
L.addAtTail(2)
L.addAtTail(1)
L.travel()
print('----尋找中間節點----')
A = L.midNode()
print(A)
print('----依據索引值獲取節點的值-----')
b = L.get(2)
print(b)
print('----依據索引進行添加值(下標從0開始)----')
L.addAtIndex(2, 6)
L.travel()
print('長度：', L.length)
print('----刪除節點(包括可以刪除頭部，尾部)----')
L.deleteNode(3)print('----根據索引值刪除指定節點(下標從0開始)----')
L.deleteAtIndex(0)
L.travel()print('----判斷是不是回文鏈表----')
L.travel()
print(L.isPalindrome())
# print(D)

2. 根據值刪除鏈表中的節點

信息

請編寫一個函數，使其可以刪除某個鏈表中給定的（非末尾）節點，你將只被給定要求被刪除的節點。

現有一個鏈表 – head = [4,5,1,9]

示例 1:

輸入: head = [4,5,1,9], node = 5
輸出: [4,1,9]
解釋: 給定你鏈表中值為 5 的第二個節點，那么在調用了你的函數之后，該鏈表應變為 4 -> 1 -> 9.
示例 2:

輸入: head = [4,5,1,9], node = 1
輸出: [4,5,9]
解釋: 給定你鏈表中值為 1 的第三個節點，那么在調用了你的函數之后，該鏈表應變為 4 -> 5 -> 9.

說明:

鏈表至少包含兩個節點。
鏈表中所有節點的值都是唯一的。
給定的節點為非末尾節點并且一定是鏈表中的一個有效節點。
不要從你的函數中返回任何結果。

答案：

class ListNode:def __init__(self, x):self.val = xself.next = Noneclass Solution:def deleteNode(self, node):""":type node: ListNode:rtype: void Do not return anything, modify node in-place instead."""node.val = node.next.valnode.next = node.next.next

3.反轉一個單鏈表

信息

反轉一個單鏈表。

示例:

輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL
進階:
你可以迭代或遞歸地反轉鏈表。你能否用兩種方法解決這道題？

答案

def reverseList(self,head,prev=None):"""反轉一個單向鏈表:param head:頭部指針:param prev:反轉后的頭結點:return: 返回反轉后的鏈表"""while head:curr = headhead = head.nextcurr.next = prevprev = currreturn prev# 遞歸思路：在return處調用自己（尾遞歸）# if not head:#     return prev## curr, head.next = head.next, prev  # 新舊鏈表的兩個方向同時前進# return self.reverseList(curr, head)

4.合并兩個有序鏈表

信息

將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。

示例：

輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4

答案

class Solution:def mergeTwoLists(self, l1: ListNode, l2: ListNode):if l1 is None and l2 is None:return None# 新建了一個值為0的頭部指針，所以我們在返回的時候要加.next(很巧妙)，這樣就不包含0這個節點了new_list = ListNode(0)pre = new_listwhile l1 is not None and l2 is not None:if l1.val < l2.val:pre.next = l1l1 = l1.nextelse:pre.next = l2l2 = l2.nextpre = pre.nextif l1 is not None:pre.next = l1else:pre.next = l2return new_list.next

5.刪除排序鏈表中的重復元素

信息

給定一個排序鏈表，刪除所有重復的元素，使得每個元素只出現一次。

示例 1:

輸入: 1->1->2
輸出: 1->2
示例 2:

輸入: 1->1->2->3->3
輸出: 1->2->3

答案

 class ListNode:def __init__(self, x):self.val = xself.next = Noneclass Solution:def deleteDuplicates(self, head: ListNode) -> ListNode:""":type head: ListNode:rtype: ListNode"""if head is None:return Noneh = ListNode(head.val)current = hflag = head.valwhile head:if flag == head.val:head = head.nextelse:current.next = ListNode(head.val)current = current.nextflag = head.valhead = head.nextreturn h

6.移除鏈表元素

信息

刪除鏈表中等于給定值 val 的所有節點。

示例:

輸入: 1->2->6->3->4->5->6, val = 6
輸出: 1->2->3->4->5

def removeElements(self, head: ListNode, val: int) -> ListNode:if head:while head.val == val:head = head.nextif head is None:return headq = headp = q.nextwhile p:if p.val == val:q.next = p.nextelse:q = q.nextp = p.nextreturn head

7.環形鏈表

信息

給定一個鏈表，判斷鏈表中是否有環。

為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環。

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個環，其尾部連接到第二個節點。

示例 2：

輸入：head = [1,2], pos = 0
輸出：true
解釋：鏈表中有一個環，其尾部連接到第一個節點。

示例 3：

輸入：head = [1], pos = -1
輸出：false
解釋：鏈表中沒有環。

進階

進階：

你能用 O(1)（即，常量）內存解決此問題嗎？

思路

• 1.快和慢兩個指針，如果有環，則一定會相遇。一個指針走一步，一個指針走兩步。

答案

 class ListNode(object):def __init__(self, x):self.val = xself.next = Noneclass Solution(object):def hasCycle(self, head):""":type head: ListNode:rtype: bool"""if not head:return Falsep1 = headp2 = head.nextwhile(1):if p1 == None or p2 == None or p2.next == None:return Falseelif p1 == p2:return Trueelse:p1 = p1.nextp2 = p2.next.next