前往此题

辅助节点法

借助辅助节点cur,dum。cur负责将遍历l1、l2，根据l1、l2的大小关系来确定添加到cur节点的顺序。
dum指向cur
因为l1,l2都是有序的，如果出现其中一个节点走到底了，另外一个直接拼接上去即可。

算法流程：

初始化cur、dum, 将dum指向cur
循环l1或者l2, 终止条件:l1或者l2为null
当l1.val < l2.val时， cur.next = l1将cur的下一个节点指向l1，l1向后走一步
否则 cur.next = l2 cur的下一个节点指向l2并且l2向后走一步
最后cur向后走一步cur=cur.next
最后合并尾部： 如果出现有剩余未合并的直接拼接到cur后即可。cur.next = l1 if l1 else l2
最终返回结果为dum.next来表示这个完整的链表

代码

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        cur = dum = ListNode(0)
        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 if l1 else l2
        return dum.next