【Python 數據結構 4.單向鏈表】

目錄

一、單向鏈表的基本概念

1.單向鏈表的概念

2.單向鏈表的元素插入

元素插入的步驟

3.單向鏈表的元素刪除

元素刪除的步驟

4.單向鏈表的元素查找

元素查找的步驟

5.單向鏈表的元素索引

元素索引的步驟

6.單向鏈表的元素修改

元素修改的步驟

二、Python中的單向鏈表

?編輯

三、單向鏈表實戰

1.面試題 02.02. 返回倒數第 k 個節點

快慢指針法

思路與算法

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

方法一雙指針判斷

方法二一次遍歷進行判斷

3.面試題 02.01. 移除重復節點

方法一、哈希表標記法

方法二、字典

四、單向鏈表的應用

MMO游戲開發 —— AOI（Area of Interest）

惟愿春日不遲，相逢終有時

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? —— 25.3.2

一、單向鏈表的基本概念

1.單向鏈表的概念

????????對于順序存儲的結構，最大的缺點就是：插入和刪除的時候需要移動大量的元素，所以基于前人的智慧，他們發明了鏈表。

????????鏈表是由一個個結點組成，每個結點之間通過鏈接關系串聯起來，每個結點都有一個后繼結點，最后一個結點的后繼結點為空結點，如圖所示：

????????由鏈接關系 A ->B 組織起來的兩個結點，B 被稱為 A的后繼結點，A 被稱為 B 的前驅結點。鏈表分為：單向鏈表、雙向鏈表、循環鏈表等等。

????????一個鏈表結點由兩部分組成：數據域 和 指針域。數據可以是任意類型，由編碼的人自行指定。指針域指向 后繼結點 的地址。一個結點包含的兩部分，如下圖所示：

2.單向鏈表的元素插入

????????單向鏈表的元素插入，就是指給定一個索引 i 和一個元素 data，生成一個值為 data 的結點，并且插入到第i個位置上。

元素插入的步驟

第1步：判斷插入位置是否合法，如果不合法則拋出異常（比如:原本只有5個元素，給定的索引是100，那顯然這個位置是不合法的）

第2步：對給定的元素，生成一個鏈表結點。

第3步：如果插入位置是 0，則直接把生成的結點的后繼結點，設置為當前的鏈表頭結點，并且把生成的結點設置為新的鏈表頭，

第4步：如果插入位置不是 0，則遍歷到插入位置的前一個位置，把生成的結點插入進來

第5步：更新鏈表的大小，即對鏈表的元素執行加一操作。

3.單向鏈表的元素刪除

????????單向鏈表的元素刪除，就是指給定一個索引 i，將從鏈表頭開始數到的第 i 個結點刪除。

元素刪除的步驟

第1步：判斷刪除位置是否合法，如果不合法則拋出異常。

第2步：如果刪除位置為首個結點，直接把鏈表頭更新為它的后繼結點，

第3步：如果刪除位置非首個結點，則遍歷到要刪除位置的前一個結點，并且把前一個結點的后繼結點設置為它后繼的后繼。

第4步：更新鏈表的大小，也就是將鏈表的大小執行減一操作。

4.單向鏈表的元素查找

????????單向鏈表的元素查找，是指在鏈表中查找指定元素 x 是否存在，如果存在則返回該結點，否則返回 null。由于需要遍歷整個鏈表進行元素對比，所以查找的時間復雜度為 (n)。

元素查找的步驟

第1步：遍歷整個鏈表，對鏈表中的每個元素，和指定元素進行比較，如果相等則返回當前遍歷到的結點;

第2步：如果遍歷完整個鏈表，都沒有找到相等的元素，則返回 NULL;

5.單向鏈表的元素索引

????????單向鏈表的元素索引，是指給定一個索引值 i，從鏈表頭結點開始數，數到第 i 個結點并且返回它，時間復雜度 O(n)。

元素索引的步驟

第1步：首先判斷給定的索引是否合法，不合法就拋出異常

第2步：直接通過索引訪問即可獲得對應的元素;

6.單向鏈表的元素修改

? ? ? ? 單向鏈表的元素修改是指將鏈表中指定索引的元素更新為新的值。

元素修改的步驟

第1步：直接通過索引訪問即可獲得對應的結點，修改成指定的值;

二、Python中的單向鏈表

class ListNode:def __init__(self, x):self.val = xself.next = Noneclass LinkedList:def __init__(self):self.head = Noneself.len = 0def size(self):return self.lendef insert(self, pos, val):if pos < 0 or pos > self.len:raise ValueError("index out of range")new_node = ListNode(val)if pos == 0:new_node.next = self.headself.head = new_nodeelse:prev = self.headfor _ in range(pos - 1):prev = prev.nextnew_node.next = prev.nextprev.next = new_nodeself.len += 1def delete(self, pos):if pos < 0 or pos >= self.size():raise ValueError("index out of range")if pos == 0:self.head = self.head.nextelse:prev = self.headfor _ in range(pos - 1):prev = prev.nextprev.next = prev.next.nextself.len -= 1def update(self, pos, val):if pos < 0 or pos >= self.size():raise ValueError("index out of range")curr = self.headfor _ in range(pos):curr = curr.nextcurr.val = valdef search(self, val):curr = self.headwhile curr:if curr.val == val:return currcurr = curr.nextreturn Nonedef index(self, val):index = 0curr = self.headwhile curr:if curr.val == val:return indexcurr = curr.nextindex += 1return -1def print(self):curr = self.headwhile curr:print(curr.val, end=" -> ")curr = curr.nextprint(None)def Test():list = LinkedList()list.insert(0, 1)list.print()list.insert(1, 1)list.print()list.insert(2, 4)list.print()list.insert(0, 1)list.print()list.insert(1, 1)list.print()list.insert(2, 4)list.print()list.update(2, 5)list.print()list.delete(2)list.print()list.insert(2, 4)list.print()list.update(4, 1)list.print()node = list.search(4)if node:print("Node found:", node.val)else:print("Node not found")x = list.index(4)print("Index of 4:", x)x = list.index(5)print("Index of 5:", x)Test()

三、單向鏈表實戰

1.面試題 02.02. 返回倒數第 k 個節點

實現一種算法，找出單向鏈表中倒數第 k 個節點。返回該節點的值。

注意：本題相對原題稍作改動

示例：
輸入： 1->2->3->4->5 和 k = 2
輸出： 4
說明：

給定的?k?保證是有效的。

快慢指針法

思路與算法

① 初始化兩個指針：fast?和?slow，它們都指向鏈表的頭節點?head。

② 移動快指針：讓?fast?指針先向前移動?k?步。

③ 同步移動快慢指針：當?fast?指針移動到鏈表的末尾時，slow?指針正好指向倒數第?k?個節點。

④ 返回結果：返回?slow?指針所指向節點的值。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def kthToLast(self, head: Optional[ListNode], k: int) -> int:fast = headslow = headwhile k > 0:fast = fast.nextk -= 1while fast:fast = fast.nextslow = slow.nextreturn slow.val

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

給定一個已排序的鏈表的頭?head?，?刪除所有重復的元素，使每個元素只出現一次?。返回?已排序的鏈表?。

示例 1：
輸入：head = [1,1,2]
輸出：[1,2]
示例 2：
輸入：head = [1,1,2,3,3]
輸出：[1,2,3]
提示：

鏈表中節點數目在范圍?[0, 300]?內
-100 <= Node.val <= 100
題目數據保證鏈表已經按升序?排列?

方法一雙指針判斷

思路與算法

① 初始化指針：curr?指針從鏈表的頭節點?head?開始。prev?指針初始化為?None，用于記錄當前節點的前一個節點。

② 遍歷鏈表：外層?while?循環用于遍歷整個鏈表，直到?curr?為?None。內層?while?循環用于處理當前節點?curr?與前一個節點?prev?值相同的情況。如果發現重復，則將?prev.next?指向?curr.next，從而跳過重復的節點。

③ 更新指針：如果沒有發現重復，則更新?prev?為當前節點?curr，并將?curr?移動到下一個節點。?

④ 返回結果：最終返回處理后的鏈表頭節點?head。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:curr = headprev = Nonewhile curr:while prev != None and curr.val == prev.val:prev.next = curr.nextcurr = prev.nextif curr == None:breakif curr == None:breakprev = currcurr = curr.nextreturn head

方法二一次遍歷進行判斷

思路與算法

① ?初始化：curr指針指向鏈表的頭節點head。

② 空鏈表處理：如果鏈表為空（curr == None），直接返回head。

?③?遍歷鏈表：如果當前節點的值curr.val與下一個節點的值curr.next.val相同，則通過curr.next = curr.next.next刪除下一個節點。如果值不相同，則移動curr指針到下一個節點。

④ 返回結果：最終返回處理后的鏈表頭節點head。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:curr = headif curr == None:return headwhile curr.next:if curr.val == curr.next.val:curr.next = curr.next.nextelse:curr = curr.nextreturn head

3.面試題 02.01. 移除重復節點

編寫代碼，移除未排序鏈表中的重復節點。保留最開始出現的節點。

示例1：
 輸入：[1, 2, 3, 3, 2, 1]
 輸出：[1, 2, 3]
示例2：
 輸入：[1, 1, 1, 1, 2]
 輸出：[1, 2]
提示：

鏈表長度在[0, 20000]范圍內。
鏈表元素在[0, 20000]范圍內。

方法一、哈希表標記法

思路與算法

① 哈希表標記法?：利用數組模擬哈希表（大小20001），用于記錄節點值是否已存在。數組下標對應節點值，元素值為1表示該值已出現過

② 雙指針遍歷：

????????tmp指針：指向當前已去重鏈表的尾節點，用于連接新節點。

? ?curr指針：遍歷原鏈表，檢查當前節點是否重復。

③ 邊界處理：?若鏈表為空直接返回；初始化時先將頭節點加入哈希表，避免后續判空操作

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def removeDuplicateNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:if head == None:return None# 哈希表hash = [0 for i in range(20001)]tmp = headcurr = head.nexthash[head.val] = 1while curr:if hash[curr.val] == 0:hash[curr.val] = 1tmp.next = currtmp = tmp.nextcurr = curr.nexttmp.next = Nonereturn head

方法二、字典

思路與算法

① ?初始化字典：首先，代碼創建了一個空字典?dict，用于存儲已經出現過的節點值。如果鏈表為空（head == None），則直接返回?None，因為空鏈表不需要去重。?

② 處理頭節點：將頭節點的值?head.val?存入字典，表示該值已經出現過。

③ 遍歷鏈表：使用?curr?指針遍歷鏈表，初始時?curr?指向頭節點。在遍歷過程中，檢查?curr.next?的值是否已經存在于字典中：如果?curr.next.val?不在字典中，說明該值尚未出現過，將其存入字典，并將?curr?指針移動到下一個節點。如果?curr.next.val?已經在字典中，說明該值是重復的，跳過該節點，即將?curr.next?指向?curr.next.next，從而刪除重復節點。

④ 返回結果：遍歷結束后，返回去重后的鏈表頭節點?head。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:def removeDuplicateNodes(self, head: Optional[ListNode]) -> Optional[ListNode]:dict = {}if head == None:return Nonedict[head.val] = 1curr = headwhile curr.next:if curr.next.val not in dict:dict[curr.next.val] = 1curr = curr.nextelse:curr.next = curr.next.next  return head