链表（精选答案）
链表(1) 相交链表
"""给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null"""A, B = headA, headBwhile A != B: A = A.next if A else headB B = B.next if B else headAreturn A(2) 反转链表
"""给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。"""cur, pre = head, Nonewhile cur: tmp = cur.next cur.next = pre pre = cur cur = tmpreturn pre(3) 回文链表
"""给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false"""vals = []while head: vals.append(head.val) head=head.nextreturn vals == vals[::-1](4) 环形链表
"""给你一个链表的头节点 head，判断链表中是否有环。"""slow = fast = headwhile fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return Truereturn False(5) 环形链表 Ⅱ
"""给定一个链表的头节点 head，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。"""slow = fast = headwhile fast and fast.next: slow = slow.next fast = fast.next.next if fast == slow: while slow != head: slow = slow.next head = head.next return slowreturn 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 = 0while 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.nextreturn dummy.next(8) 删除链表的倒数第 N 个节点
"""给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。"""left = right = dummy = ListNode(next=head)for _ in range(n): right = right.nextwhile right.next: left = left.next right = right.nextleft.next = left.next.nextreturn dummy.next(9) 两两交换链表中的节点
"""给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。输入：head = 输出："""node0 = dummy = ListNode(next=head)node1 = headwhile node1 and node1.next: node2 = node1.next node3 = node2.next node0.next = node2 node2.next = node1 node1.next = node3 node0 = node1 node1 = node3return dummy.next(10) k 个一组翻转链表
"""给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。"""n = 0node = headwhile 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_startreturn 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 Nonehashmap = {}cur = headwhile cur: hashmap = Node(cur.val) cur = cur.nextcur = headwhile cur: hashmap.next = hashmap.get(cur.next) hashmap.random = hashmap.get(cur.random) cur = cur.nextreturn hashmap(12) 排序链表
"""给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表。"""def sortList(self, head): """ :type head: Optional :rtype: Optional """ 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] :rtype: Optional """ n = len(lists) if n == 0: return None if n == 1: return lists left = self.mergeKLists(lists[:n//2]) right = self.mergeKLists(lists) 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 = Noneclass 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 self.move_node_to_last(node) return node.val def put(self, key, value): if key in self.hashmap: node = self.hashmap node.val = value self.move_node_to_last(node) return if len(self.hashmap) == self.capacity: del self.hashmap self.remove_node(self.head.next) node = ListNode(key, value) self.hashmap = 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)
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]