leetcdeo链表之合并链表
2022-03-20 本文已影响0人
小奚有话说
21、合并两个有序链表
文章出现的代码都是python3
题目
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例2：
输入：l1 = [], l2 = []
输出：[]
示例3：
输入：l1 = [], l2 = [0]
输出：[0]
思路：
解法1：递归
递归就是假定递归后的链表的是已经处理好的链表，这个时候，就需要考虑几种边界状态
1、l1为空，那么直接返回l2，同理l2为空返回l1
2.当l1，l2都不为空，那么比较l1，l2的大小，那么就需要将处理好的链表拼接到较小的链表后面即可
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1: return l2
if not l2: return l1
if l1.val < l2.val:
l1.next = self.mergeTwoLists1(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists1(l1, l2.next)
解法2：迭代
一般迭代的话，创建一个虚拟的头结点，会比较好处理
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
if not l1 or not l2: return l1 or l2
cur = head = ListNode()
# 当l1，l2不为空的时候，按照顺序将结点拼接到cur后面
while l1 and l2:
if l1.val <= l2.val:
cur.next, l1 = l1, l1.next
else :
cur.next, l2 = l2, l2.next
cur = cur.next
# 此时l1和l2至少有一个为空
cur.next = l1 or l2
return head.next
23、合并K个有序链表
文章出现的代码都是python3
题目
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-k-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
示例2：
输入：lists = []
输出：[]
示例3：
输入：lists = [[]]
输出：[]
思路
合并K个有序链表，可以在合并两个有序链表，进行多个链表的合并。
解法1
按顺序进行多个链表的合并
class Solution:
# 合并两个有序链表
def mergeTwoLists(self, l1:ListNode, l2:ListNode) -> ListNode:
if not l1 or not l2: return l1 or l2
cur = head = ListNode()
while l1 and l2:
if l1.val < l2.val:
cur.next, l1 = l1, l1.next
else:
cur.next, l2 = l2, l2.next
cur = cur.next
cur.next = l1 or l2
return head.next
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
if not lists: return lists
ans = lists[0]
for item in lists[1:]:
ans = self.mergeTwoLists(ans, item)
return ans
解法2
采用两两进行合并的方式进行合并，也叫分治
class Solution:
def mergeTwoLists(self, l1:ListNode, l2:ListNode) -> ListNode:
if not l1 or not l2: return l1 or l2
cur = head = ListNode()
while l1 and l2:
if l1.val < l2.val:
cur.next, l1 = l1, l1.next
else:
cur.next, l2 = l2, l2.next
cur = cur.next
cur.next = l1 or l2
return head.next
# l和r是左右两个指针，当l==r的时候，也就是递归到了最小的单位（一个链表元素）
# 如果l和r没有相遇，也就是需要合并的结果，返回合并后的结果即可
def merge(self, lists, l, r):
if l == r: return lists[l]
if l > r: return None
mid = (l + r) >> 1
return self.mergeTwoLists(self.merge(lists, l, mid), self.merge(lists, mid+1, r))
def mergeKLists1(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
return self.merge(lists, 0, len(lists) - 1)
1669、合并两个链表
题目：
给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。
请你将 list1 中下标从 a 到 b 的全部节点都删除，并将list2 接在被删除节点的位置。
示例1：
输入：list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
输出：[0,1,2,1000000,1000001,1000002,5]
示例2：
输入：list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
输出：[0,1,1000000,1000001,1000002,1000003,1000004,6]
思路：
找到下标a的前一个结点，和下标b的结点，然后和list2进行拼接
class Solution:
# 返回step步后的结点
def next(self, head, step):
cur = head
while step and cur:
cur = cur.next
step -= 1
return cur
# 返回链表的尾结点
def tail(self, head):
cur = head
while cur.next:
cur = cur.next
return cur
def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
vHead = ListNode(0, list1)
# 通过找list1中下标a的前置结点，和下标b的结点，进行拼接
prev = self.next(vHead, a)
last = self.next(prev.next, b - a)
prev.next = list2
tail = self.tail(list2)
tail.next = last.next
return vHead.next
