6-2 两个有序链表序列的合并 (15 分)

题目中给定了两个序列，我们需要将它们合并成一个序列。

常用的合并方法有合并排序和归并排序。这里介绍一下合并排序的思路。

合并排序的核心思想：分治法。将一个大问题分解为若干小问题，递归求解小问题后再将小问题合并解决大问题。

具体实现方法：将待排序序列分成两部分，分别递归排序，然后将两个有序序列合并成一个大的有序序列。

代码实现：

def merge_sort(nums):
n = len(nums)
if n <= 1:
return nums
mid = n // 2
left = merge_sort(nums[:mid])
right = merge_sort(nums[mid:])
return merge(left, right)

def merge(left, right):
result = []
i, j = 0, 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result

merged_nums = merge_sort([6, 5, 3, 1, 8, 7, 2, 4])
print(merged_nums)

使用该方法，即可将题目中给定的两个序列合并成一个有序序列，并输出。

注意：题目中给定的序列需要先转化为数组或列表再进行处理。该方法最坏时间复杂度为 O(nlogn)。