博客 / 詳情

返回

鏈表（精選答案）

鏈表

(1) 相交鏈表

"""
給你兩個單鏈表的頭節點 headA 和 headB ，請你找出並返回兩個單鏈表相交的起始節點。如果兩個鏈表不存在相交節點，返回 null
"""
A, B = headA, headB
while A != B:
    A = A.next if A else headB 
    B = B.next if B else headA
return A

(2) 反轉鏈表

"""
給你單鏈表的頭節點 head ，請你反轉鏈表，並返回反轉後的鏈表。
"""
cur, pre = head, None
while cur:
    tmp = cur.next
    cur.next = pre
    pre = cur
    cur = tmp
return pre

(3) 迴文鏈表

"""
給你一個單鏈表的頭節點 head ，請你判斷該鏈表是否為迴文鏈表。如果是，返回 true ；否則，返回 false
"""
vals = []
while head:
    vals.append(head.val)
    head=head.next
return vals == vals[::-1]

(4) 環形鏈表

"""
給你一個鏈表的頭節點 head，判斷鏈表中是否有環。
"""
slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
        return True
return False

(5) 環形鏈表 Ⅱ

"""
給定一個鏈表的頭節點 head，返回鏈表開始入環的第一個節點。 如果鏈表無環，則返回 null。
"""
slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if fast == slow:
        while slow != head:
            slow = slow.next
            head = head.next
        return slow
return None

(6) 合併兩個有序鏈表

"""
將兩個升序鏈表合併為一個新的 升序 鏈表並返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。
"""
def mergeTwoLists(self, list1, list2):
    if list1 == None:
        return list2
    if list2 == None:
        return list1
    while list1.val < list2.val:
        list1.next = self.mergeTwoLists(list1.next, list2)
        return list1
    list2.next = self.mergeTwoLists(list2.next, list1)
    return list2

(7) 兩數相加

"""
給你兩個非空的鏈表，表示兩個非負的整數。它們每位數字都是按照逆序的方式存儲的，並且每個節點只能存儲一位數字。請你將兩個數相加，並以相同形式返回一個表示和的鏈表。
"""
cur = dummy = ListNode()
carry = 0
while l1 or l2 or carry:
    carry += (l1.val if l1 else 0) + (l2.val if l2 else 0)
    cur.next = ListNode(carry%10)
    carry //= 10
    cur = cur.next
    if l1:
        l1 = l1.next
    if l2:
        l2 = l2.next
return dummy.next

(8) 刪除鏈表的倒數第 N 個節點

"""
給你一個鏈表，刪除鏈表的倒數第 n 個結點，並且返回鏈表的頭結點。
"""
left = right = dummy = ListNode(next=head)
for _ in range(n):
    right = right.next
while right.next:
    left = left.next
    right = right.next
left.next = left.next.next
return dummy.next

(9) 兩兩交換鏈表中的節點

"""
給你一個鏈表，兩兩交換其中相鄰的節點，並返回交換後鏈表的頭節點。你必須在不修改節點內部的值的情況下完成本題（即，只能進行節點交換）。
輸入：head = [1,2,3,4]
輸出：[2,1,4,3]
"""
node0 = dummy = ListNode(next=head)
node1 = head
while node1 and node1.next:
    node2 = node1.next
    node3 = node2.next
    
    node0.next = node2
    node2.next = node1
    node1.next = node3

    node0 = node1
    node1 = node3
return dummy.next

(10) k 個一組翻轉鏈表

"""
給你鏈表的頭節點 head ，每 k 個節點一組進行翻轉，請你返回修改後的鏈表。k 是一個正整數，它的值小於或等於鏈表的長度。如果節點總數不是 k 的整數倍，那麼請將最後剩餘的節點保持原有順序。
"""
n = 0
node = head
while node:
    n += 1
    node = node.next    
group_pre = dummy = ListNode(next=head)
cur = head 
while n >= k:
    n -= k
    pre = None
    for _ in range(k):
        nxt = cur.next
        cur.next = pre
        pre = cur
        cur = nxt
    group_start = group_pre.next
    group_start.next = cur
    group_pre.next = pre    
    group_pre = group_start
return dummy.next

(11) 隨機鏈表的複製

"""
給你一個長度為 n 的鏈表，每個節點包含一個額外增加的隨機指針 random ，該指針可以指向鏈表中的任何節點或空節點。
構造這個鏈表的 深拷貝。 深拷貝應該正好由 n 個 全新 節點組成，其中每個新節點的值都設為其對應的原節點的值。新節點的 next 指針和 random 指針也都應指向複製鏈表中的新節點，並使原鏈表和複製鏈表中的這些指針能夠表示相同的鏈表狀態。複製鏈表中的指針都不應指向原鏈表中的節點。
https://leetcode.cn/problems/copy-list-with-random-pointer/?envType=study-plan-v2&envId=top-100-liked
"""
if not head:
    return None
hashmap = {}
cur = head
while cur:
    hashmap[cur] = Node(cur.val)
    cur = cur.next
cur = head
while cur:
    hashmap[cur].next = hashmap.get(cur.next)
    hashmap[cur].random = hashmap.get(cur.random)
    cur = cur.next
return hashmap[head]

(12) 排序鏈表

"""
給你鏈表的頭結點 head ，請將其按 升序 排列並返回 排序後的鏈表。
"""
def sortList(self, head):
    """
    :type head: Optional[ListNode]
    :rtype: Optional[ListNode]
    """
    if not head or not head.next:
        return head
    slow = fast = head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    mid = slow.next
    slow.next = None
    left = self.sortList(head)
    right = self.sortList(mid)
    return self.merge(left, right)

def merge(self, left, right):
    cur = dummy = ListNode(0)
    while left and right:
        if left.val < right.val:
            cur.next = left
            left = left.next
        else:
            cur.next = right
            right = right.next
        cur = cur.next
    if left:
        cur.next = left
    if right:
        cur.next = right
    return dummy.next

(13) 合併 K 個升序鏈表

"""
給你一個鏈表數組，每個鏈表都已經按升序排列。請你將所有鏈表合併到一個升序鏈表中，返回合併後的鏈表。
"""
def mergeKLists(self, lists):
    """
    :type lists: List[Optional[ListNode]]
    :rtype: Optional[ListNode]
    """
    n = len(lists)
    if n == 0:
        return None
    if n == 1:
        return lists[0]
    left = self.mergeKLists(lists[:n//2])
    right = self.mergeKLists(lists[n//2:])
    return self.merge(left, right)
    
def merge(self, left, right):
    cur = dummy = ListNode()
    while left and right:
        if left.val < right.val:
            cur.next = left
            left = left.next
        else:
            cur.next = right
            right = right.next
        cur = cur.next
    if left:
        cur.next = left
    if right:
        cur.next = right
    return dummy.next

(14) LRU 緩存

class ListNode:
    def __init__(self, key=0, val=0):
        self.key = key
        self.val = val
        self.prev = None
        self.next = None

class LRUCache:

    def __init__(self, capacity):
        self.capacity = capacity
        self.hashmap = {}
        self.head = ListNode()
        self.tail = ListNode()
        self.head.next = self.tail
        self.tail.prev = self.head    

    def get(self, key):
        if key not in self.hashmap:
            return -1
        node = self.hashmap[key]
        self.move_node_to_last(node)
        return node.val

    def put(self, key, value):
        if key in self.hashmap:
            node = self.hashmap[key]
            node.val = value
            self.move_node_to_last(node)
            return
        if len(self.hashmap) == self.capacity:
            del self.hashmap[self.head.next.key]
            self.remove_node(self.head.next)
        node = ListNode(key, value)
        self.hashmap[key] = node
        self.add_node_to_last(node)
        
    def remove_node(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
    
    def add_node_to_last(self, node):
        self.tail.prev.next = node
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev = node
    
    def move_node_to_last(self, node):
        self.remove_node(node)
        self.add_node_to_last(node)
後端
user avatar
0 位用戶收藏了這個故事！

發佈 評論

Some HTML is okay.