21题有序链表的合并

LeetCode刷题之21题有序链表的合并

难度:easy 思路:硬算

一、题目描述

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例:

1
2
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

二、问题分析

有序链表的合并是归并排序中的经典算法,这题采用常规思路即可解决问题,唯一要注意的点是当指针p、q中任一指针为空时后续应该如何操作。

三、代码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def mergeTwoLists(self, l1, l2,):
p = l1
q = l2
head = None
# p q均不为空
while p != None and q != None:
if p.val <= q.val :
if head == None:
head = p
n = p
p = p.next
else:
n.next = p
n = n.next
p = p.next
else :
if head == None:
head = q
n = q
q = q.next
else:
n.next = q
n = n.next
q = q.next
# p q中任一为空 将p指定为非空 直接将p后面的节点连在n的后面
if p == None and q !=None:
p = q
q = None
if head == None:
head = p
n = p
else:
n.next = p

return head

时间复杂度分析:

O(M+N) M为l1链表的长度,N为l2链表的长度