蜜臀无码在线,免费美女网站,日本淫乱网站,青青操影院,爱射综合,免费看黄色A片,中文字幕亚洲精品,亚洲成人毛片

AI作者：田旭

AI編輯：田旭

1 知識點

1.1 什么是鏈表

提到鏈表，我們大家都不陌生，在平時的編碼中我們也或多或少地使用過這個數據結構。算法（第4版） (豆瓣)一書中對鏈表的定義如下：

鏈表是一種遞歸的數據結構，它或者為空（null），或者是指向一個結點（node）的引用，該節(jié)點還有一個元素和一個指向另一條鏈表的引用。

鏈表（Linked list）是一種常見的基礎數據結構，是一種線性表，但是并不會按線性的順序存儲數據，而是在每一個節(jié)點里存到下一個節(jié)點的指針(Pointer)。由于不必須按順序存儲，鏈表在插入的時候可以達到O(1)的復雜度，比另一種線性表順序表快得多，但是查找一個節(jié)點或者訪問特定編號的節(jié)點則需要O(n)的時間，而順序表相應的時間復雜度分別是O(logn)和O(1)。

使用鏈表結構可以克服數組鏈表需要預先知道數據大小的缺點，鏈表結構可以充分利用計算機內存空間，實現靈活的內存動態(tài)管理。但是鏈表失去了數組隨機讀取的優(yōu)點，同時鏈表由于增加了結點的指針域，空間開銷比較大。

1.2 鏈表結構

1.2.1 單向鏈表

鏈表中最簡單的一種是單向鏈表，它包含兩個域，一個信息域和一個指針域。這個鏈接指向列表中的下一個節(jié)點，而最后一個節(jié)點則指向一個空值。

一個單向鏈表包含兩個值: 當前節(jié)點的值和一個指向下一個節(jié)點的鏈接

一個單向鏈表的節(jié)點被分成兩個部分。第一個部分保存或者顯示關于節(jié)點的信息，第二個部分存儲下一個節(jié)點的地址。單向鏈表只可向一個方向遍歷。

1.2.2 雙向鏈表

一種更復雜的鏈表是“雙向鏈表”或“雙面鏈表”。每個節(jié)點有兩個連接：一個指向前一個節(jié)點，（當此“連接”為第一個“連接”時，指向空值或者空列表）；而另一個指向下一個節(jié)點，（當此“連接”為最后一個“連接”時，指向空值或者空列表）。

一個雙向鏈表有三個整數值: 數值, 向后的節(jié)點鏈接, 向前的節(jié)點鏈接

雙向鏈表也叫雙鏈表。雙向鏈表中不僅有指向后一個節(jié)點的指針，還有指向前一個節(jié)點的指針。這樣可以從任何一個節(jié)點訪問前一個節(jié)點，當然也可以訪問后一個節(jié)點，以至整個鏈表。一般是在需要大批量的另外儲存數據在鏈表中的位置的時候用。雙向鏈表也可以配合下面的其他鏈表的擴展使用。

1.2.3 循環(huán)鏈表

在一個 循環(huán)鏈表中, 首節(jié)點和末節(jié)點被連接在一起。這種方式在單向和雙向鏈表中皆可實現。要轉換一個循環(huán)鏈表，你開始于任意一個節(jié)點然后沿著列表的任一方向直到返回開始的節(jié)點。再來看另一種方法，循環(huán)鏈表可以被視為“無頭無尾”。這種列表很利于節(jié)約數據存儲緩存，假定你在一個列表中有一個對象并且希望所有其他對象迭代在一個非特殊的排列下。

指向整個列表的指針可以被稱作訪問指針。

用單向鏈表構建的循環(huán)鏈表

1.3鏈表相關的核心點

null/nil 異常處理
dummy node 啞巴節(jié)點
快慢指針
插入一個節(jié)點到排序鏈表
從一個鏈表中移除一個節(jié)點
翻轉鏈表
合并兩個鏈表
找到鏈表的中間節(jié)點

2 常見題型

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

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

思路：直接法，遇到重復就跳過

class Solution:    def deleteDuplicates(self, head: ListNode) -> ListNode:        cur = head        while cur and cur.next:            if cur.val == cur.next.val:                cur.next = cur.next.next            else:                cur = cur.next        return head

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

給定一個排序鏈表，刪除所有含有重復數字的節(jié)點，只保留原始鏈表中 沒有重復出現 的數字。

思路：定義啞節(jié)點指向鏈表頭，定義雙指針，一個指向當前節(jié)點，一個指向前一個節(jié)點。當有重復的元素時，cur指向下一位，直到下一位與當前節(jié)點不相等，用flag標記表示有重復數字，當循環(huán)完畢，pre的下一位指向cur的下一位，flag標記歸位

當沒有重復數字，pre指向cur

class Solution:    def deleteDuplicates(self, head: ListNode) -> ListNode:        if not head or not head.next:  # 空鏈表或單即節(jié)點鏈表            return head
        dummy = ListNode(0)    # 定義啞節(jié)點        dummy.next = head        pre = dummy            # 啞節(jié)點指針        cur = head             # 鏈表指針        flag = False           # 標記是否重復        while cur:            while cur.next and pre.next.val == cur.next.val:                cur = cur.next   # 將所有重復節(jié)點標記為True                flag = True            if flag is True:     # 重復節(jié)點就跳過                pre.next = cur.next                flag = False            else:                pre = cur        # 不重復就下一個節(jié)點            cur = cur.next        return dummy.next

206. 反轉鏈表

反轉一個單鏈表。

思路1：迭代，每次存儲前一個節(jié)點，并讓當前節(jié)點的next指針指向前一個節(jié)點

思路2：遞歸，假設我子節(jié)點下的所有節(jié)點都已經反轉好了，現在就剩我和我的子節(jié)點沒有完成最后的反轉了，所以反轉一下我和我的子節(jié)點。

# 迭代class Solution:    def reverseList(self, head: ListNode) -> ListNode:        pre = None        cur = head        while cur:            temp = cur.next   # 存儲節(jié)點的下一位            cur.next = pre    # 指向前驅節(jié)點            pre = cur                     cur = temp        # cur指向原來的下一位        return pre

# 遞歸class Solution:    def reverseList(self, head: ListNode) -> ListNode:        if not head or not head.next:            return head        p = self.reverseList(head.next)        head.next.next = head        head.next = None        return p

92. 反轉鏈表 II

反轉從位置 m 到 n 的鏈表。請使用一趟掃描完成反轉。

思路：用雙指針法，現將慢指針移動到要反轉的部分的前一個節(jié)點，用另一個指針指向慢指針后面的節(jié)點，然后兩兩交換節(jié)點

class Solution:    def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:        dummy = ListNode(None)        dummy.next = head        pre = dummy        for i in range(1, m):            pre = pre.next         # 前驅指針移動到位置m        cur = pre.next        for i in range(m, n):      # 兩兩交換節(jié)點            temp = cur.next                    cur.next = temp.next   # cur一直不變，只修改指針到下一個位置            temp.next = pre.next   # temp.next指向pre的next，也就是最新的第m個位置            pre.next = temp        # 更新temp為最新的第m個位置        return pre

21. 合并兩個有序鏈表

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

思路：建立新鏈表，依次按升序鏈接兩個鏈表的元素

class Solution:    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:        dummy = ListNode(None)        pre = dummy        while l1 and l2:            if l1.val < l2.val:                pre.next = l1                l1 = l1.next            else:                pre.next = l2                l2 = l2.next            pre = pre.next        pre.next = l1 if l1 else l2        return dummy.next

86. 分隔鏈表

給定一個鏈表和一個特定值 x，對鏈表進行分隔，使得所有小于 x 的節(jié)點都在大于或等于 x 的節(jié)點之前。

思路：創(chuàng)建雙鏈表，一個存儲小于x的值，一個存儲大于x的值

class Solution:    def partition(self, head: ListNode, x: int) -> ListNode:        before = befornHead = ListNode(None)        after = afterHead = ListNode(None)        while head:            if head.val < x:                before.next = head                before = before.next            else:                after.next = head                after = after.next            head = head.next            after.next = None        before.next = afterHead.next        return befornHead.next

148. 排序鏈表

在 O(n log n) 時間復雜度和常數級空間復雜度下，對鏈表進行排序。

思路：歸并排序，找中點和合并操作

# 歸并排序（遞歸），空間復雜度O(n)class Solution:    def sortList(self, head: ListNode) -> ListNode:        if not head or not head.next:            return head        slow, fast = head, head.next        while fast and fast.next:            slow, fast = slow.next, fast.next.next        mid = slow.next        slow.next = None        left = self.sortList(head)        right = self.sortList(mid)        h = res = ListNode(0)        while left and right:            if left.val < right.val:                 h.next, left = left, left.next            else:                 h.next, right = right, right.next            h = h.next        h.next = left if left else right        return res.next

# 快速排序class Solution:    def sortList(self, head: ListNode) -> ListNode:        if head is None:            return head        # 分成三個鏈表，分別是比軸心數小，相等，大的數組成的鏈表        big = None        small = None        equal = None        cur = head        while cur:            temp = cur            cur = cur.next            if temp.val < head.val:                temp.next = small                small = temp            elif temp.val > head.val:                temp.next = big                big = temp            else:                temp.next = equal                equal = temp        # 拆完各自排序即可，equal 無需排序        big = self.sortList(big)        small = self.sortList(small)
        ret = ListNode(None)        cur = ret        # 將三個鏈表組合成一起        # 可以同時返回鏈表的頭指針和尾指針加速鏈表的合并。        for p in [small, equal, big]:            while p is not None:                cur.next = p                p = p.next                cur = cur.next            cur.next = None        return ret.next

143. 重排鏈表

給定一個單鏈表 L：L0→L1→…→L**n-1→Ln ，將其重新排列后變?yōu)椋?em>L0→Ln→L1→Ln-1→L2→Ln-2→…

思路：找到中點斷開，翻轉后面部分，然后合并前后兩個鏈表

class Solution:    def reorderList(self, head: ListNode) -> None:        """        Do not return anything, modify head in-place instead.        """        if not head or not head.next:            return head        slow, fast = head, head        # 找到鏈表中點        while fast.next and fast.next.next:               slow = slow.next            fast = fast.next.next        # 反轉后半部分        print(slow.next)        right = None        cur = slow.next        while cur:            temp = cur.next            cur.next = right            right = cur            cur = temp        # 將反轉的后半部分插入到前半部分        left = head        while left and right:            slow.next = right.next            right.next = left.next            left.next = right            left = right.next            right = slow.next

141. 環(huán)形鏈表

給定一個鏈表，判斷鏈表中是否有環(huán)。

思路1：哈希表，統(tǒng)計每個元素出現的次數

思路2：快慢指針，快慢指針相同則有環(huán)，證明：如果有環(huán)每走一步快慢指針距離會減 1

# 哈希表class Solution:    def hasCycle(self, head: ListNode) -> bool:        dic = {}        while head:            if head in dic:                return True            else:                dic[head] = 1            head = head.next        return False

# 快慢指針class Solution:    def hasCycle(self, head: ListNode) -> bool:        if head is None or head.next is None:            return False        slow = head        fast = slow.next        while fast and fast.next:            fast = fast.next.next            slow = slow.next            if fast == slow:                return True        return False

142. 環(huán)形鏈表 II

給定一個鏈表，返回鏈表開始入環(huán)的第一個節(jié)點。如果鏈表無環(huán)，則返回 null。

思路：快慢指針，快慢相遇之后，慢指針回到頭，快慢指針步調一致一起移動，相遇點即為入環(huán)點

class Solution:    def detectCycle(self, head: ListNode) -> ListNode:        fast, slow = head, head        while True:            if not (fast and fast.next):                return             slow = slow.next            fast = fast.next.next            if slow == fast:                break        fast = head        while fast != slow:            fast = fast.next            slow = slow.next        return fast

138. 復制帶隨機指針的鏈表

給定一個鏈表，每個節(jié)點包含一個額外增加的隨機指針，該指針可以指向鏈表中的任何節(jié)點或空節(jié)點。
要求返回這個鏈表的 深拷貝。

思路：1、hash 表存儲指針，2、復制節(jié)點跟在原節(jié)點后面

class Solution:    def copyRandomList(self, head: 'Node') -> 'Node':        if not head:            return        dic = {}        dic[None] = None        cur = head        while cur:            if cur not in dic:                dic[cur] = Node(cur.val)     # 將當前未拷貝的節(jié)點放入字典中            if cur.random not in dic:                dic[cur.random] = Node(cur.random.val)   # 將當前未拷貝的random指針放入字典中            dic[cur].random = dic[cur.random]            if cur.next not in dic:                dic[cur.next] = Node(cur.next.val)     # 將當前未拷貝的next指針放入字典中            dic[cur].next = dic[cur.next]            cur = cur.next        return dic[head]

234. 回文鏈表

請判斷一個鏈表是否為回文鏈表。

思路1：將值復制到數組中，時間復雜度O(n)，空間復雜度O(n)

思路2：快慢指針，先找到鏈表中點，然后反轉后半部分，再與前半部分比較，時間復雜度O(n)，空間復雜度O(1)

# 將值復制到數組中class Solution:    def isPalindrome(self, head: ListNode) -> bool:        visit = []        cur = head        while cur:            visit.append(cur.val)            cur = cur.next        return visit == visit[::-1]

# 找中點 -> 反轉 -> 比較class Solution:    def isPalindrome(self, head: ListNode) -> bool:        pre = None        slow, fast = head, head        while fast and fast.next:            slow = slow.next      # 使慢指針指向中間節(jié)點            fast = fast.next.next        while slow:  # 反轉后半部分，pre指向反轉部分            temp = slow.next            slow.next = pre            pre = slow            slow = temp        while head and pre:   # 比較兩部分是否相同            if head.val != pre.val:                return False            head = head.next            pre = pre.next        return True