21.合并两个有序链表
题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路
方法1：递归
如果 l1 或者 l2 一开始就是空链表 ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 l1 和 l2 哪一个链表的头节点的值更小，然后递归地决定下一个添加到结果里的节点。如果两个链表有一个为空，递归结束。
方法2：迭代
当 l1 和 l2 都不是空链表时，判断 l1 和 l2 哪一个链表的头节点的值更小，将较小值的节点添加到结果里，当一个节点被添加到结果里之后，将对应链表中的节点向后移一位。
代码
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
迭代法
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
if l1 is None:
return l2
elif l2 is None:
return l1
else:
p = l1
q = l2
l3 = ListNode()
r = l3 # r表示l3单链表的尾指针
while p and q: # 注意：此处的循环判断条件为 p and q
if p.val <= q.val: # p指针指向的元素小，将此元素并入结果链表
node = ListNode(p.val)
# 尾插法构建链表
r.next = node
r = r.next
# 工作指针指向当前链表中的下一个节点
p = p.next
else: # q指针指向的元素小，将此元素并入结果链表
node = ListNode(q.val)
r.next = node
r = r.next
q = q.next
if p is not None:
r.next = p
elif q is not None:
r.next = q
return l3.next
def mergeTwoLists1(self, l1, l2): # 1 2 3 1 3 4
"""
递归法
"""
if l1 is None:
return l2
elif l2 is None:
return l1
elif l1.val < l2.val:
l1.next = self.mergeTwoLists1(l1.next, l2)
return l1
else:
l2.next = self.mergeTwoLists1(l1, l2.next)
return l2
def len_linked_list(self, linked_list):
"""
返回单链表的长度
:param linked_list:需要返回其长度的单链表
:return:单链表的长度
"""
p = linked_list
n = 0
while p is not None:
n += 1
p = p.next
return n
def print_linked_list(self, linked_list) -> None:
"""
打印单链表中的所有元素
:param linked_list: 单链表
:return: 无
"""
print("----------------------------------------")
pointer = linked_list
while pointer is not None:
print(pointer.val)
pointer = pointer.next
def create_linked_list(self, list):
"""根据list中的所有元素构建单链表"""
l = ListNode() # 单链表头节点
r = l # 起始尾指针r指向头节点
for e in list:
node = ListNode(e)
r.next = node
r = r.next
return l.next
if __name__ == "__main__":
slt = Solution()
l1 = slt.create_linked_list([1, 2, 4])
l2 = slt.create_linked_list([1, 3, 4])
slt.print_linked_list(l1)
slt.print_linked_list(l2)
l3 = slt.mergeTwoLists1(l1, l2)
slt.print_linked_list(l3)