21. 合并两个有序链表(easy)

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

• show the code:

# 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:
        res = ListNode(0)
        node = res
        while l1 and l2:
            if l1.val < l2.val:
                node.next,l1 = l1,l1.next
            else:
                node.next,l2 = l2,l2.next
            node = node.next
        if l1:
            node.next = l1
        else:
            node.next = l2
        return res.next

• 主要是要熟悉链表的遍历，新建哑节点，同时赋值给res，方便最后返回哑节点的next。
• 判断过程类似于归并排序的合并过程，如果链表1此节点值小于链表2节点值，那么将链表1节点赋给新链表节点，链表1向下遍历一个节点，相反大于或等于的话则处理链表2，直到链表1或者链表2某一个达到尾节点为止，同时新链表也要向下遍历。
• 这里要注意链表1与链表2不等长的情况，将较短的那个链表走完之后，直接将较长链表剩余部分接到新链表后面即可。
• 最后返回哑节点的下一个节点即可（注意，这里不是我们中间处理的新链表节点）