一、思維導圖

二、鏈表的反轉

    def reverse(self):"""思路：1、設置previous_node、current、next_node三個變量,目標是將current和previous_node逐步向后循環并逐步進行反轉,知道所有元素都被反轉2、但唯一的問題是：一旦current.next反轉為向前,current的后繼元素就將不再被記錄3、所以設置一個next_node用于在反轉開始前,current將后繼元素賦值給next_node。4、開始反轉5、反轉后將current和previous_node向后移動一次,然后重復以上3-5步驟:return:"""previous_node = Nonecurrent = self.headwhile current:next_node = current.next  # 記錄下一個節點,因為等會current的next要反轉了，先保存以免丟失current.next = previous_node  # 反轉節點previous_node = current  # 移動previouscurrent = next_node  # 移動next_node,由于next_node已經被記錄，所以即使current.next變成了前面的元素，但后面的元素也能找到。# print(current.data, end="--->")self.head = previous_node  # 最后把self.head補上

三、合并兩個有序鏈表

    def merge_sorted_lists(self, other_list):"""思路：1、創建i、j用于確定次數(之所以函數中的ij就能確定次數，是因為合并兩個有序列表實際上的目標是：將其中一個列表在與另一個列表的對比中，逐漸消耗到0,即排序完成),只要其中一個完成了不用管另一個完成了沒有直接加到尾部就行了，而ij正是這種設計，知道i,j的某一個達到對應列表的最大值(排序完成)才跳出第一個循環2、創建p、q兩個"指針"用于遍歷各自的鏈表3、翻轉兩個鏈表方便對比，因為這是單項升序表4、刪除鏈表1的原節點注意事項：1、當self鏈表為空時直接反轉other鏈表并拷貝,other為空則不變2、判空"""# 任意鏈表為空則無操作if self.size == 0 and other_list.size == 0:returnelif self.size == 0:# 如果 self 是空的，就將 other_list 反轉拷貝進來other_list.reverse()p = other_list.headwhile p:self.add_tail(p.data)p = p.nextself.reverse()self.size = other_list.sizereturnelif other_list.size == 0:return  # self 不變# 記錄 self 原有節點數量pre_size = self.size# 反轉兩個鏈表（升序→降序）self.reverse()other_list.reverse()# 準備兩個指針，遍歷 self 和 other_listq = self.headp = other_list.headi = j = 0while i < pre_size and j < other_list.size:if q.data >= p.data:self.add_tail(q.data)q = q.nexti += 1else:self.add_tail(p.data)p = p.nextj += 1# 4. 把剩下的節點繼續添加到尾部while i < pre_size:self.add_tail(q.data)q = q.nexti += 1while j < other_list.size:self.add_tail(p.data)p = p.nextj += 1# 5. 刪除 self 原來的 pre_size 個“舊節點”for _ in range(pre_size):self.delete_head()# 6. 恢復升序結構self.reverse()# 7. 更新 sizeself.size = pre_size + other_list.size

四、鏈表完整實現

"""
目的：解決順序表存儲空間有上限、刪除和插入效率低等問題(因為是按照簡單的列表索引儲存的,每次插入刪除需要騰位操作)。
鏈表：鏈式存儲的線性表，使用隨機的物理內存 存儲邏輯上相連的數據。注意點：
1、 用q進行處理時q指向的就是實際鏈表的Node對象，因為q和node都是可變對象，這實際上是一種引用綁定，兩者在賦值后指向同一個對象(Node)
2、 插入某個值時一定要先將下一個節點的位置給新節點保存，再將新節點的位置給前一個節點保存，順序不可變。因為下一個節點的位置只有上一個節點知道，如果上一個節點先改為保存新的節點，下一個節點的位置就沒有任何節點知道了。
"""class Node():"""1】 包含存儲數據元素的數據域2】有一個存儲下一個節點位置的位置域"""def __init__(self, data):self.data = data  # 普通節點的數據域self.next = None  # 普通節點的位置域class LinkedList():"""鏈表"""def __init__(self, node=None):self.size = 0  # 頭節點的數據域self.head = node  # 頭節點的位置域,用于記錄第一個節點的位置,可認為實際上就是下一個節點的整體(就通過next保存的位置來讀取下一個Node整體)，\# 不單單是位置，這個整體包含了下一個節點的下一個節點的位置和下一個節點的數據。def add_head(self, value):"""功能：將頭插的方式插入到頭節點的后面注意事項：1、插入成功鏈表長度自增。2、申請Node節點，封裝:param:value：需要插入的節點的數據:return:"""node = Node(value)  # 創建一個全新的節點node.next = self.head  # 先將下一個節點的位置給新節點保存self.head = node  # 再將節點作為第一個節點給seld.head保存self.size += 1def add_tail(self, value):"""功能：將一個新的節點插入到鏈表的尾部:param value::return:"""if self.is_empty():self.add_head(value)  # 如果為空直接用add_headelse:q = self.head  # 創建一個q用于尋找節點尾部的位置while q.next != None:q = q.nextq.next = Node(value)  # 將找到的尾部None賦值為新的節點self.size += 1def add_index(self, index, value):"""通過q找到需要插入的位置冰進行處理,用q進行處理時q指向的就是實際鏈表的Node對象，因為q和node都是可變對象，這實際上是一種引用綁定，兩者在賦值后指向同一個對象(Node):param value::param index::return:"""if index > self.size + 1 or index <= 0:returnelse:if index == 1:self.add_head(value)else:q = self.headi = 1while i < index - 1:q = q.nexti += 1node = Node(value)node.next = q.next  # 先將新的next指向后面的node,否則后面的node的位置沒有人記錄鏈就斷了(故此行代碼不可與下行順序調換)q.next = nodeself.size += 1def delete_head(self):"""刪除第一個節點:return:"""if self.is_empty():returnelse:self.head = self.head.nextself.size -= 1def delete_tail(self):"""功能：尾刪,刪除最后一個節點:param value::return:"""# 判空if self.is_empty():print("刪除失敗")returnelif self.size == 1:  # 當鏈表只有一個結點時self.head = Noneelse:# 找到最后一個結點的前一個節點q = self.headi = 1while i < self.size - 1:q = q.nexti += 1# 刪除q.next = None  # q.next = q.next.nextself.size -= 1def delete_index(self, index):"""通過q找到需要插入的位置冰進行處理,用q進行處理時q指向的就是實際鏈表的Node對象，因為q和node都是可變對象，這實際上是一種引用綁定，兩者在賦值后指向同一個對象(Node):param value::param index::return:"""# 判空、判斷位置是否合理if self.is_empty() or index > self.size or index <= 0:print("位置錯誤")returnelse:if index == 1:  # 當索引為1時直接修改self.head.dataself.head = self.head.nextelse:q = self.head  # 創建q用于尋找需要修改的節點i = 1while i < index - 1:q = q.nexti += 1q.next = q.next.nextself.size -= 1def change_index(self, index, value):"""按位置修改:param index::param value::return:"""if self.is_empty() or index > self.size or index <= 0:print("錯誤")returnelse:if index == 1:  # 當索引為1時直接修改self.head.dataself.head.data = valueelse:q = self.head  # 創建q用于尋找需要修改的節點i = 1  # i用于確定循環次數while i < index - 1:q = q.nexti += 1q.data = value  # 對找到的節點進行賦值# 按值修改def change_value(self, o_value, n_value):""":param o_value::param n_value::return:"""if self.is_empty() or o_value == n_value:print("無需修改")returnelse:q = self.headwhile q:if q.data == o_value:q.data = n_valuereturnq = q.nextprint("查無此數據")def find_value(self, value):"""按值查找:param value::return:"""if self.is_empty():"鏈表為空空空空空空空空空"returnelse:q = self.headi = 1while i <= self.size:if q.data == value:return i + 1q = q.nexti += 1print("未找到數據")  # 如果到最后還沒有return說明沒有該數據return Nonedef is_empty(self):return self.size == 0def show(self):"""從頭到尾打印出節點的數據域中的數據,用q進行處理時q指向的就是實際鏈表的Node對象(但如果對q進行賦值則不是這樣，那就是普通的賦值而已并不改變實際的Node)，因為q和node都是可變對象，這實際上是一種引用綁定，兩者在賦值后指向同一個對象(Node):return:"""if self.is_empty():returnelse:q = self.head  # 此時self.head已經在add_head時指向了第一個Node，故可以進一步訪問Node的data和下Node的next（即下一個Node）while q:print(q.data, end="->")q = q.nextprint()  # 換行def reverse(self):"""思路：1、設置previous_node、current、next_node三個變量,目標是將current和previous_node逐步向后循環并逐步進行反轉,知道所有元素都被反轉2、但唯一的問題是：一旦current.next反轉為向前,current的后繼元素就將不再被記錄3、所以設置一個next_node用于在反轉開始前,current將后繼元素賦值給next_node。4、開始反轉5、反轉后將current和previous_node向后移動一次,然后重復以上3-5步驟:return:"""previous_node = Nonecurrent = self.headwhile current:next_node = current.next  # 記錄下一個節點,因為等會current的next要反轉了，先保存以免丟失current.next = previous_node  # 反轉節點previous_node = current  # 移動previouscurrent = next_node  # 移動next_node,由于next_node已經被記錄，所以即使current.next變成了前面的元素，但后面的元素也能找到。# print(current.data, end="--->")self.head = previous_node  # 最后把self.head補上def merge_sorted_lists(self, other_list):pre_size = self.size # 先記錄一下排序之前的self.size，用于之后覺得執行頭刪操作的次數self.reverse()other_list.reverse()i = 0j = 0write = self.headq = self.head  # 創建一個q用于尋找節點的位置p = other_list.head  # 創建一個p用于尋找other節點的位置while write.next != None:write = write.nextwhile i < self.size and j < other_list.size:if q.data >= p.data:write.next = Node(q.data)write = write.nextq = q.nexti += 1else:write.next = Node(p.data)write = write.nextp = p.nextj += 1while j < other_list.size:write.next = Node(p.data)write = write.nextj += 1while i < self.size:write.next = Node(q.data)write = write.nexti += 1self.size=pre_size+other_list.sizefor i in range(pre_size):self.show()self.delete_head()self.reverse()if __name__ == '__main__':# 創建單向鏈表linkList = LinkedList()linkList.add_tail(10)linkList.add_tail(20)linkList.add_tail(30)linkList.add_tail(40)linkList.add_tail(50)linkList.add_tail(60)linkList_2 = LinkedList()linkList_2.add_tail(15)linkList_2.add_tail(25)linkList_2.add_tail(35)linkList_2.add_tail(45)linkList_2.add_tail(55)linkList_2.add_tail(65)linkList_2.add_tail(999)linkList_2.show()linkList.merge_sorted_lists(linkList_2)linkList.show()