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

示例：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/merge-two-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

方法一：双指针遍历

数据结构经典的单链表题，对我来说难点在于怎么用python实现指针的操作。
经过搜索后发现其实特别简单...（或者说并不需要严格意义上的指针）

思路：两个链表已经按元素值递增次序排序，将其合并时，均从第一个结点起进行比较，将小的结点链入链表中，同时后移工作指针。该问题既然要求返回一个升序链表，那么用尾插法即可。比较结束后，可能有一个链表会为空，此时用尾插法将剩下的结点依次插入新链表中。

需要注意的是：本体的单链表并没有头结点，所以不能直接将l1或l2置空，需要新建一个单链表用来保存结果。（希望大神可以赐教不用新建表的解法）

# 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:
        
        l3 = ListNode(-1)
        r = l3

        pa = l1
        pb = l2

        while pa and pb:
            
            if pa.val <= pb.val:
                r.next = pa
                pa = pa.next
            else:
                r.next = pb
                pb = pb.next

            r = r.next
        
        if pa:
            r.next = pa

        if pb:
            r.next = pb

        return l3.next