LeetCode刷题 NO.21 合并两个有序链表 (简单)

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

示例

输入：l1 = [1,2,4], l2 = [1,3,4]

输出：[1,1,2,3,4,4]

解析

1）要解决这个问题，得先介绍一下创建链表的方法，思路一样

2）依次比较两个链表当前节点的值，谁小就把谁接到目标链上

3）如果有一个先走完，直接把另一个接到目标链上即可

代码示例

1、补充链表创建方法

class ListNode():
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

def create_link(lst):
    root = ListNode(0)
    node = root
    for i in lst:
        node.next = ListNode(i)
        node = node.next
    return root.next

def print_link(lk):
    while lk:
        print(lk.val)
        lk = lk.next

lk1 = create_link([1,2,4])
print_link(lk1)

2、合并两个有序链表

def mergeTwoLists(list1, list2):
    root = ListNode(0)
    node = root
    while list1 and list2:
        if list1.val < list2.val:
            node.next = list1
            list1 = list1.next
        else:
            node.next = list2
            list2 = list2.next
        node = node.next
    if list1:
        node.next = list1
    if list2:
        node.next = list2
    return root.next

lk1 = create_link([1,2,4])
lk2 = create_link([1,3,4])

lk3 = mergeTwoLists(lk1, lk2)
print_link(lk3)