出一道关于线性表的题目并写出思路、输入输出实例和对应代码

题目：给定两个有序链表，将它们合并为一个新的有序链表。

思路：合并两个有序链表可以使用双指针法，定义两个指针分别指向两个链表的头节点，比较它们的值的大小，将小的节点加入新的链表中，然后移动指针继续比较。最后，将还未遍历完的链表直接加入新的链表中即可。

代码：

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

def mergeTwoLists(l1: Node, l2: Node) -> Node:
    dummy = Node(0)
    cur = dummy
    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 dummy.next

输入输出实例：

# 输入: 1->2->4, 1->3->4
# 输出: 1->1->2->3->4->4

l1 = Node(1, Node(2, Node(4)))
l2 = Node(1, Node(3, Node(4)))
merged_list = mergeTwoLists(l1, l2)
cur = merged_list
while cur:
    print(cur.val, end=" ")
    cur = cur.next
# 输出：1 1 2 3 4 4

其中，`Node`类用于定义链表节点，函数`mergeTwoLists`用于合并两个有序链表，时间复杂度为O(m+n)，空间复杂度为O(1)，其中m和n分别为两个链表的长度。