链表（精选答案）

链表

(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)