在Python语言中利用原空间实现带头节点的单链表有序表合成有序表

在Python中，我们可以使用原地操作（in-place）的方式合并两个已排序的带头节点的单链表，使其保持有序。这里假设每个链表节点有一个额外的属性`val`表示其值，以及一个指向下一个节点的指针`next`。以下是步骤：

1. **创建一个空头节点**：定义一个新的头节点，`dummy_head`，它的`val`设为负无穷大，以便于判断新的列表开始。

2. **遍历两个链表**：设置两个指针，一个指向`dummy_head`（`p = dummy_head`），另一个分别从每个链表的头部开始（如`l1_head`和`l2_head`）。同时维护两个当前元素的最小值，初始化为各自链表的第一个元素。

3. **比较并插入**：如果`l1_head`的`val`小于或等于`l2_head`的`val`，将`l1_head`移到`p.next`，然后`p`移动到`l1_head`；否则相反。这样保证每次操作后`p.next`总是包含较小的元素。

4. **更新链表头**：遍历结束后，`p.next`就是合并后的有序链表的头节点。

以下是伪代码示例：

def merge_sorted_lists(l1_head, l2_head):
    dummy_head = ListNode(-float('inf'))
    p = dummy_head

    while l1_head and l2_head:
        if l1_head.val <= l2_head.val:
            p.next = l1_head
            l1_head = l1_head.next
        else:
            p.next = l2_head
            l2_head = l2_head.next
        p = p.next

    # 如果其中一个链表还有剩余元素，将其连接至新链表末尾
    if l1_head:
        p.next = l1_head
    elif l2_head:
        p.next = l2_head

    return dummy_head.next