?203.移除鏈表元素

Python鏈表節點定義：

class ListNode:def __init__(self, val, next=None):self.val = valself.next = next

性能分析

鏈表的特性和數組的特性進行一個對比，如圖所示：

203. 移除鏈表元素

這道題就是給大家一個鏈表，移除鏈表中等于某個target的所有節點。然后返回這個鏈表的頭節點。

如果我們刪除這個節點的話，讓這個節點的前一個節點，指向這個節點的下一個節點。這樣我們就把這個元素從列表中移除了。

移除節點時有一個問題。如果移除的節點是頭節點，頭節點沒有前一個節點，我們要把Head向下移1位 ?head=head.next。這樣我們就把頭結點，從鏈表中刪除了。他的新的頭結點是原來的第二個節點。

從列表中移除元素針對頭節點和非頭節點的移除元素的方式是不一樣的。
那么我們在實現這段代碼邏輯的時候就要做一個判斷，我們刪除的這個節點是不是頭節點？這樣的話我們刪除節點的方式就沒有統一，能不能有一種方式能統一的方式刪除所有節點？
還有一種方法叫做虛擬頭結點的方法：就是在這個列表中再加入一個頭節點。這個頭節點叫做dummy head。是虛擬的。這樣的話我們再去刪除列表中的元素時，所有的元素都可以按照一個規則進行刪除。

不用虛擬頭節點來刪除代碼中元素的方法：

首先我們要判斷我們刪除的元素是不是頭節點。
這個頭節點一定要不為空，因為我們接下來要取這個頭節點的值。如果這個頭節點為空的話，我們相當于取了一個空指針，編譯的時候會報錯。同時這個頭節點的數值等于我們要刪除的值。滿足這樣的情況時，我們要把這個頭節點刪掉。
if (head != null and head->val == target)
我們進行移除頭節點的操作后，移動到下一個節點時發現還是一樣。所以我們移除頭節點其實是一個持續移除的過程。所以這里應該是while。
while (head != null and head->val == target)head = head->nextcur  = head
這里的臨時指針為什么是從head開始而不是從它的下一個節點開始？例如說我現在要刪除第二個元素。刪除第二個元素要找他的上一個節點指向他的下一個節點。所以這里要記錄該節點的上一個節點。所以我們要刪除head.next要從head開始。
whlie(cur != null && cur.next != null){
這兩個值不能為空，否則在取值時會出現空指針錯誤。if (cur->next->val == target){cur->next = cur->next->next}else {cur = cur->next}return head

用虛擬頭節點的方法：

首先將dummyhead的實例化,new出來一個節點
dummyhead = new ListNode()
dummyhead->next = head
定義一個臨時指針來遍歷鏈表，頭節點的指針是不能改的。否則最后返回的頭節點一直在變化。
cur = dummyhead 
這里為什么不定義cur = dummyhead.next？我們如果要刪掉一個元素，必須要知道這個元素的上一個元素是什么。
while(cur->next != null){if (cur->next->val == target){cur->next = cur->next->next;else{cur = cur->next}
return dummyhead->next
為什么不返回head？因為head有可能已經被我們刪掉了。

Python代碼：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:dummyhead = ListNode()dummyhead.next = headcur = dummyheadwhile cur.next != None:if cur.next.val == val:cur.next = cur.next.nextelse:cur = cur.nextreturn dummyhead.next

707. 設計鏈表

?

Python代碼：

class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass MyLinkedList:def __init__(self):self.dummy_head = ListNode()self.size = 0def get(self, index: int) -> int:if index < 0 or index >= self.size:return -1current = self.dummy_head.nextfor i in range(index):current = current.nextreturn current.valdef addAtHead(self, val: int) -> None:self.dummy_head.next = ListNode(val, self.dummy_head.next)self.size += 1def addAtTail(self, val: int) -> None:current = self.dummy_headwhile current.next:current = current.nextcurrent.next = ListNode(val)self.size += 1def addAtIndex(self, index: int, val: int) -> None:if index < 0 or index > self.size:returncurrent = self.dummy_headfor i in range(index):current = current.nextcurrent.next = ListNode(val, current.next)self.size += 1def deleteAtIndex(self, index: int) -> None:if index < 0 or index >= self.size:returncurrent = self.dummy_headfor i in range(index):current = current.nextcurrent.next = current.next.nextself.size -= 1# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

206. 反轉鏈表

Python代碼：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:pre =Nonecur = headwhile cur:temp = cur.nextcur.next = prepre = curcur = tempreturn pre方法二：
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def reverse(self, cur: Optional[ListNode], pre: Optional[ListNode]) ->Optional[ListNode]:if cur == None:return pretemp = cur.nextcur.next = prereturn self.reverse(temp, cur)def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:return self.reverse(head, None)