LeetBook - 数据结构教程(第 6 版) - 在线编程实训
第二章 线性表
进度条：25(或24)/25
链表的题，虽然不难吧，但写起来还是要思考一下的，有时候还需要在纸上模拟一下，这还是不够熟练啊~ 😂
2.1 顺序表及其应用
1. 二进制求和
Python
class Solution:
def addBinary(self, a: str, b: str) -> str:
n1, n2 = len(a), len(b)
res = []
c, base = 0, 2
i, j = n1 - 1, n2 - 1
while i >= 0 and j >= 0:
c, r = divmod(int(a[i]) + int(b[j]) + c, base)
res.append(str(r))
i -= 1
j -= 1
while i >= 0:
c, r = divmod(int(a[i]) + c, base)
res.append(str(r))
i -= 1
while j >= 0:
c, r = divmod(int(b[j]) + c, base)
res.append(str(r))
j -= 1
if c == 1:
res.append('1')
return ''.join(res[::-1])
2. 移除元素
Python
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
n = len(nums)
length = 0
for i in range(n):
if nums[i] != val:
nums[length] = nums[i]
length += 1
return length
2.2 有顺序表及其应用
1. 删除有序数组中的重复项
Python
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
n = len(nums)
length = 0
for i in range(1, n):
if nums[i] != nums[length]:
length += 1
nums[length] = nums[i]
length += 1
return length
2. 删除有序数组中的重复项 II
Python
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
n = len(nums)
length = 1
for i in range(2, n):
if nums[i] != nums[length - 1]:
length += 1
nums[length] = nums[i]
length += 1
return length
3. 合并两个有序数组
Python
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
i, j = m - 1, n - 1
k = m + n - 1
while i >= 0 and j >= 0:
if nums1[i] >= nums2[j]:
nums1[k] = nums1[i]
i -= 1
else:
nums1[k] = nums2[j]
j -= 1
k -= 1
while j >= 0:
nums1[k] = nums2[j]
j -= 1
k -= 1
4. 寻找两个正序数组的中位数
注：困难题，要求时间复杂度为 ~
排序，时间复杂度 为 ，不合题意！！！
这题不算做出来了吧~ 😂
Python
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
nums = nums1 + nums2
nums.sort()
n = len(nums)
return 1.0 * nums[n // 2] if n & 1 else (nums[n // 2 - 1] + nums[n // 2]) / 2
时间复杂度 为 的解法，待补充~
Python
# 待补充2.3 链表的实现
1. 设计链表
方法一：使用 单链表 实现~
Python
class LinkedNode:
def __init__(self, val: int, next=None) -> None:
self.val = val
self.next = next
class MyLinkedList:
def __init__(self):
# 头结点
# head.val 保存链表长度
# head.next 指向链表的第一个结点
self.head = LinkedNode(val=0)
def get(self, index: int) -> int:
if index >= self.head.val:
return -1
ptr, idx = self.head.next, 0
while idx < index:
ptr = ptr.next
idx += 1
return ptr.val
def addAtHead(self, val: int) -> None:
node = LinkedNode(val=val)
node.next = self.head.next
self.head.next = node
self.head.val += 1
def addAtTail(self, val: int) -> None:
node = LinkedNode(val=val)
ptr = self.head
while ptr.next:
ptr = ptr.next
node.next = ptr.next
ptr.next = node
self.head.val += 1
def addAtIndex(self, index: int, val: int) -> None:
if index == 0:
self.addAtHead(val)
elif index == self.head.val:
self.addAtTail(val)
elif 0 < index < self.head.val:
node = LinkedNode(val=val)
ptr, idx = self.head, 0
while idx < index:
ptr = ptr.next
idx += 1
node.next = ptr.next
ptr.next = node
self.head.val += 1
def deleteAtIndex(self, index: int) -> None:
if 0 <= index < self.head.val:
ptr, idx = self.head, 0
while idx < index:
ptr = ptr.next
idx += 1
pnxt = ptr.next
ptr.next = pnxt.next
del pnxt
self.head.val -= 1
方法二：使用 双链表 实现~
Python
from dataclasses import dataclass
@dataclass
class DoublyLinkedNode:
val: int = 0
prev: 'DoublyLinkedNode' = None
next: 'DoublyLinkedNode' = None
class MyLinkedList:
def __init__(self):
self.head = DoublyLinkedNode(val=0)
self.tail = self.head
def get(self, index: int) -> int:
if index >= self.head.val:
return -1
ptr, pnxt = None, None
if index <= self.head.val // 2:
ptr = self.head.next
pnxt = lambda ptr: ptr.next
else:
ptr = self.tail
pnxt = lambda ptr: ptr.prev
index = self.head.val - index - 1
idx = 0
while idx < index:
ptr = pnxt(ptr)
idx += 1
return ptr.val
def addAtHead(self, val: int) -> None:
node = DoublyLinkedNode(val=val)
if self.tail == self.head:
node.prev = self.head
node.next = self.head.next
self.head.next = node
self.tail = node
else:
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
self.head.val += 1
def addAtTail(self, val: int) -> None:
node = DoublyLinkedNode(val=val)
node.prev = self.tail
node.next = self.tail.next
self.tail.next = node
self.tail = node
self.head.val += 1
def addAtIndex(self, index: int, val: int) -> None:
ptr, pnxt = None, None
if index == 0:
self.addAtHead(val)
elif index == self.head.val:
self.addAtTail(val)
elif 0 < index < self.head.val:
if index <= self.head.val // 2:
ptr = self.head.next
pnxt = lambda ptr: ptr.next
else:
ptr = self.tail
pnxt = lambda ptr: ptr.prev
index = self.head.val - index - 1
idx = 0
while idx < index:
ptr = pnxt(ptr)
idx += 1
node = DoublyLinkedNode(val=val)
node.prev = ptr.prev
ptr.prev.next = node
node.next = ptr
ptr.prev = node
self.head.val += 1
def deleteAtIndex(self, index: int) -> None:
if 0 <= index < self.head.val:
ptr, pnxt = None, None
if index <= self.head.val // 2:
ptr = self.head.next
pnxt = lambda ptr: ptr.next
else:
ptr = self.tail
pnxt = lambda ptr: ptr.prev
index = self.head.val - index - 1
idx = 0
while idx < index:
ptr = pnxt(ptr)
idx += 1
if ptr == self.tail:
self.tail = ptr.prev
else:
ptr.next.prev = ptr.prev
ptr.prev.next = ptr.next
del ptr
self.head.val -= 1
下面这段代码重复了好多次，可以用一个函数把它封装起来~
PS：根据 index 和链表长度的关系，选择从 head.next 或 tail 开始遍历链表~
Python
ptr, pnxt = None, None
if index <= self.head.val // 2:
ptr = self.head.next
pnxt = lambda ptr: ptr.next
else:
ptr = self.tail
pnxt = lambda ptr: ptr.prev
index = self.head.val - index - 1
2. 链表随机节点
方法一：借助 辅助空间，等概率随机选择 交给 库函数~ 😂
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def __init__(self, head: Optional[ListNode]):
self.data = []
ptr = head
while ptr:
self.data.append(ptr.val)
ptr = ptr.next
def getRandom(self) -> int:
# return self.data[random.randint(0, len(self.data) - 1)]
return choice(self.data)
进阶：
- 如果链表非常大且长度未知，该怎么处理？
- 你能否在不使用额外空间的情况下解决此问题？
方法二：水塘抽样~
参考 官方题解 ~
从链表头开始，遍历整个链表，对遍历到的第 个结点，随机选择区间 内的一个整数，如果其等于 ，则将返回结果置为该结点值，否则不变。
该算法会保证每个节点的值成为最后被返回的值的概率均为 ，证明如下：
PS：学习了~ 🤣
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def __init__(self, head: Optional[ListNode]):
self.head = head
def getRandom(self) -> int:
res, i = 0, 1
ptr = self.head
while ptr:
if randrange(i) == 0:
res = ptr.val
i += 1
ptr = ptr.next
return res
——2023年7月19日
2.4 单链表及其应用
1. 移除链表元素
方法一：使用 哑结点，统一删除操作~
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
# 创建头结点/哑结点，统一删除操作
# head 指向链表的第一个结点
dummy = ListNode()
dummy.next = head
pre, ptr = dummy, dummy.next
while ptr:
if ptr.val == val:
pre.next = ptr.next
else:
pre = ptr
ptr = ptr.next
return dummy.next
方法二：特殊考虑删除第一个结点的情况~
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
while head and head.val == val:
head = head.next
pre, ptr = None, head
while ptr:
if ptr.val == val:
pre.next = ptr.next
else:
pre = ptr
ptr = ptr.next
return head
2. 删除链表中的节点
一般情况下，要想删除单链表中的某个结点 node，需要知道 node 前驱结点的指针，此时只需要从头结点 head 开始遍历，找到 node 前驱结点即可。但是，这里我们并不知道指向 head 结点的指针，又想删除 node 结点怎么办呢？
答案是，只需要用 node 后继结点的值覆盖 node 结点的值即可~
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def deleteNode(self, node):
"""
:type node: ListNode
:rtype: void Do not return anything, modify node in-place instead.
"""
pre, ptr = None, node
while ptr.next:
ptr.val = ptr.next.val
pre = ptr
ptr = ptr.next
pre.next = None
3. 反转链表
方法一：迭代(头插法) ~
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
ptr = head
head = ListNode()
while ptr:
pnxt = ptr.next
ptr.next = head.next
head.next = ptr
ptr = pnxt
return head.next
方法二：迭代(直接反转) ~
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
pre, ptr = None, head
while ptr:
pnxt = ptr.next
ptr.next = pre
pre = ptr
ptr = pnxt
return pre
方法三：递归 ~
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 递归出口
if head is None or head.next is None:
return head
# 见上面图示
neo_head = self.reverseList(head.next)
head.next.next = head
head.next = None
return neo_head
4. 反转链表 II
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
dummy = ListNode()
dummy.next = head
n = right - left + 1
lptr, rptr = dummy, dummy
for i in range(right):
if i >= n:
lptr = lptr.next
rptr = rptr.next
# lptr: 第 left 个结点的前一个结点
# rptr: 第 right 个结点
while lptr.next != rptr:
lpnxt = lptr.next
lptr.next = lpnxt.next
lpnxt.next = rptr.next
rptr.next = lpnxt
return dummy.next
5. 奇偶链表
第一次迭代：
第二次迭代：
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None:
return head
# p 指向当前奇偶索引排序后最后一个奇数索引结点
# q 指向当前奇偶索引排序后最后一个偶数索引结点
p, q = head, head.next
while q and q.next:
# r 指向下一个要插入的奇数索引结点
r = q.next
q.next = r.next
r.next = p.next
p.next = r
p = p.next
q = q.next
return head
6. 分隔链表
不纠结了！直接将原链表拆分成两个链表，一个 val < x，另一个 val >= val，最后再合并~
直接在原链表中修改指针，目测会很麻烦，下次再补充吧~ 😂
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
if head is None or head.next is None:
return head
left = ListNode()
right = ListNode()
ptr = head
lptr = left
rptr = right
while ptr:
pnxt = ptr.next
if ptr.val < x:
ptr.next = lptr.next
lptr.next = ptr
lptr = lptr.next
else:
ptr.next = rptr.next
rptr.next = ptr
rptr = rptr.next
ptr = pnxt
lptr.next = right.next
return left.next
7. 两两交换链表中的节点
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
dummy.next = head
# 交换 ptr 与 ptr.next
pre, ptr = dummy, dummy.next
while ptr and ptr.next:
pnxt = ptr.next
ptr.next = pnxt.next
pnxt.next = ptr
pre.next = pnxt
pre = ptr
ptr = ptr.next
return dummy.next
8. 链表的中间结点
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 计算链表长度
n = 0
ptr = head
while ptr:
n += 1
ptr = ptr.next
# 查找链表中间结点，即第 n // 2 + 1 个结点
n = n // 2 + 1
idx = 1
ptr = head
while idx < n:
ptr = ptr.next
idx += 1
return ptr
9. 回文链表
反转前半部分链表，时间复杂度 ，空间复杂度 ~
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
# 计算链表长度
n = 0
ptr = head
while ptr:
n += 1
ptr = ptr.next
# 反转前半部分链表
pre, ptr = None, head
for _ in range(n // 2):
pnxt = ptr.next
ptr.next = pre
pre = ptr
ptr = pnxt
# 此时，pre 指向第 n // 2 个结点，ptr 指向第 n // 2 + 1 个结点
# 如果链表长度 n 为奇数，让 ptr 指向第 n // 2 + 2 个结点，即：
# 当 n 为偶数时，pre 和 ptr 分别指向链表的两个中心结点
# 当 n 为奇数时，pre 和 ptr 分别指向中心结点两侧的两个结点
if n & 1:
ptr = ptr.next
# 回文判断
while ptr:
if pre.val != ptr.val:
return False
pre = pre.next
ptr = ptr.next
return True
—— 2023年7月20日
10. 重排链表
先反转后半部分链表，然后将后半部分反转链表插入到前半部分链表中~
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
"""
Do not return anything, modify head in-place instead.
"""
# 计算链表长度
n = 0
ptr = head
while ptr:
n += 1
ptr = ptr.next
# 找到链表的后半部分
# 当 n 为偶数数，后半部分从第 n // 2 + 1 个结点开始
# 但 n 为奇数时，后半部分从第 n // 2 + 2 个结点开始
# 所以我们先找到第 n // 2 和 第 n // 2 + 1 个结点
# 即，前半部分链表的最后一个结点 pre
# 和后半部分链表的第一个结点 ptr
idx = n // 2
pre, ptr = None, head
while idx > 0:
pre = ptr
ptr = ptr.next
idx -= 1
# 如果 n 为奇数，pre, ptr 向前走一步
# 分别指向第 n // 2 + 1 和 n // 2 + 2 个结点
if n & 1:
pre = ptr
ptr = ptr.next
pre.next = None
# 此时 pre 指向链表前半部分的最后一个结点
# ptr 指向链表后半部分的第一个结点
# 然后，将链表第二部分结点反转
pre = None
while ptr:
pnxt = ptr.next
ptr.next = pre
pre = ptr
ptr = pnxt
# pre 指向后半部分链表反转后的第一个结点，即原链表的最后一个结点
# 接下来，将 pre 指向的后半部分反转链表插入到 head 指向的前半部分链表
ptr = head
while pre:
pnxt = pre.next
pre.next = ptr.next
ptr.next = pre
ptr = pre.next
pre = pnxt
return head
11. 对链表进行插入排序
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 附设哑结点，统一插入操作
dummy = ListNode()
dummy.val = -inf
dummy.next = head
# 将链表分成两个链表
# 一个是代表有序区的有序链表
# 一个是代表无序区的无序链表
# 有序区初始化为链表第一个结点
# 无序区为第二个结点到最后一个结点
# node 遍历无序区的每个结点，并将它插入到有序区
node = head.next
head.next = None
while node:
# 从有序区的开始位置查找插入位置
pre, ptr = dummy, dummy.next
while ptr and ptr.val <= node.val:
pre = ptr
ptr = ptr.next
# 将 node 插入到 pre 之后
pnext = node.next
node.next = pre.next
pre.next = node
# 将 node 指向下一个要插入的结点
node = pnext
return dummy.next
12. K 个一组翻转链表
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
# 链表长度
n = 0
ptr = head
while ptr:
n += 1
ptr = ptr.next
dummy = ListNode()
# tail：指向上一次反转后的尾结点
# ptr: 指向当前要反转的连续 k 个结点的第一个结点
# 也是反转后的尾结点
tail = dummy
ptr = head
# 执行 n // k 反转次数
for _ in range(n // k):
# 反转 ptr 之后的 k 个结点
# ptr 是反转后的尾结点
# 先保存一下
tmp = ptr
# 反转连续 k 个结点
pre = None
for _ in range(k):
pnxt = ptr.next
ptr.next = pre
pre = ptr
ptr = pnxt
# pre 为反转后第一个结点
tail.next = pre
tail = tmp
tail.next = ptr
return dummy.next
13. 分隔链表
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:
# 链表长度
n = 0
ptr = head
while ptr:
n += 1
ptr = ptr.next
# 每个子链表的长度，从大到小
q, r = divmod(n, k)
length = [q] * k
for i in range(r):
length[i] += 1
# 分割链表
# ptr 指向每个子链表的第一个结点
# 初始指向 head，即第一个子链表的第一个结点
res = []
ptr = head
for i in range(k):
# 第 i 个子链表的长度
m = length[i]
# ptr 为空，或者 m == 0
# 说明第 i 个子链表为空
if ptr is None:
res.append(None)
continue
res.append(ptr)
# 因为要将第 i 个子链表最后一个结点的 next 域置空
# 因此，需要记录 ptr 的前驱结点 pre
pre = None
while m > 0:
pre = ptr
ptr = ptr.next
m -= 1
# 最后 pre 指向第 i 个链表的最后一个结点
# ptr 指向下一个子链表，即第 i + 1 个子链表的第一个结点
pre.next = None
return res
2.5 有序链表及其应用
1. 删除排序链表中的重复元素
Python
# 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]:
if head is None:
return head
# pre 指向删除重复元素后的子链表的最后一个结点
pre, ptr = head, head.next
while ptr:
if ptr.val == pre.val:
ptr = ptr.next
else:
pre.next = ptr
pre = ptr
ptr = ptr.next
pre.next = None
return head
2. 删除排序链表中的重复元素 II
双指针/滑动窗口 ~
Python
# 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]:
dummy = ListNode()
dummy.next = head
# ptr: 指向删除重复数组后的最后一个结点
# left: 指向连续数字的开始结点
# right: 指向连续数字最后一个结点的下一个结点
# 区间 [left, right) 即为要删除的连续数字结点
ptr, left = dummy, dummy.next
while left:
right = left.next
while right and right.val != left.val:
ptr, left = left, right
right = right.next
if right:
while right and right.val == left.val:
right = right.next
ptr.next = right
left = right
return dummy.next
3. 合并两个有序链表
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
head = ListNode()
ptr = head
ptr1, ptr2 = list1, list2
while ptr1 and ptr2:
if ptr1.val <= ptr2.val:
pnxt = ptr1.next
ptr1.next = ptr.next
ptr.next = ptr1
ptr = ptr1
ptr1= pnxt
else:
pnxt = ptr2.next
ptr2.next = ptr.next
ptr.next = ptr2
ptr = ptr2
ptr2 = pnxt
ptr.next = ptr1 if ptr1 else ptr2
return head.next
4. 合并K个升序链表
比较暴力，先就这么的吧~ 🤣
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
n = len(lists)
if n == 0:
return None
head = ListNode()
ptr = head
heads = [lists[i] for i in range(n)]
while True:
min_val = inf
idx = -1
cnt = 0
for i in range(n):
if heads[i] is None:
cnt += 1
continue
if heads[i].val < min_val:
idx = i
min_val = heads[i].val
if cnt >= n - 1:
if cnt == n - 1:
ptr.next = heads[idx]
break
pnxt = heads[idx].next
heads[idx].next = ptr.next
ptr.next = heads[idx]
ptr = heads[idx]
heads[idx] = pnxt
return head.next
分治法 ~
—— 2023年8月12日
Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
def merge2Lists(l1: 'ListNode',
l2: 'ListNode') -> 'ListNode':
if l1 is None or l2 is None:
return l1 if l1 else l2
head = ListNode()
p, p1, p2 = head, l1, l2
while p1 and p2:
if p1.val <= p2.val:
p.next = p1
p1 = p1.next
else:
p.next = p2
p2 = p2.next
p = p.next
p.next = p1 if p1 else p2
return head.next
def merge(p: int, r: int) -> 'ListNode':
if p == r:
return lists[p]
if p > r:
return None
q = (p + r) >> 1
l1 = merge(p, q)
l2 = merge(q + 1, r)
return merge2Lists(l1, l2)
return merge(0, len(lists) - 1)
—— 2023年7月21日
评论 (3)
