输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

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

限制：

0 <= 链表长度 <= 1000

注意：本题与主站21题相同。

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

class Solution:
    def mergeTwoLists(self, l1, l2):

解题思路：

• 根据题目描述，链表$l1,l2$是递增的，因此容易想到使用双指针$l1$和$l2$遍历两链表，根据$l1.val$和$l2.val$的大小关系确定节点添加顺序，两节点指针交替前进，直至遍历完毕。
• 引入伪头节点：由于初始状态合并链表中无节点，因此循环第一轮时无法将节点添加到合并链表中。解决方案：初始化一个辅助节点$dum$作为合并链表的伪头节点，将各节点添加至$dum$之后。

算法流程：

1. 初始化：伪头节点$dum$，节点$cur$指向$dum$。
2. 循环合并：当$l1$或$l2$为空时跳出；
   1. 当$l1.val<l2.val$时，$cur$的后继节点指定为$l1$，同时$l1$向前走一步；
   2. 当$l1.val>=l2.val$：$cur$的后继节点指定为$l2$，同时$l2$向前走一步；
   3. 节点$cur$向前走一步，即$cur=cur.next$。
3. 合并剩余尾部：跳出时有两种情况，即$l1$为空或$l2$为空。
   1. 若$l1 \neq null$：将$l1$添加至节点$cur$之后；
   2. 否则：将$l2$添加至节点$cur$之后。
4. 返回值：合并链表在伪头节点$dum$之后，因此返回$dum.next$即可。

复杂度分析：

• 时间复杂度$O(M+N)$：$M,N$分别为链表$l1,l2$的长度，合并操作需遍历两链表。
• 空间复杂度$O(1)$：节点引用$dum,cur$使用常数大小的额外空间。

class Solution:
	def mergeTwoLists(self, l1, l2):
		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