合并链表代码

合并两个有序链表的代码如下所示：

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

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode(-1)
    prev = dummy
    while l1 and l2:
        if l1.val < l2.val:
            prev.next = l1
            l1 = l1.next
        else:
            prev.next = l2
            l2 = l2.next
        prev = prev.next
    prev.next = l1 if l1 else l2
    return dummy.next

其中，我们使用了一个哑结点(dummy)来简化代码实现。在循环中，我们判断当前两个链表头结点的值，将较小的结点接到prev指针后面，然后将该链表头结点指针后移，继续比较，直到其中一个链表为空。最后，将剩余的链表接到合并链表的末尾即可。

注意，该代码实现的时间复杂度为$O(m+n)$，其中m和n分别为两个链表的长度。

相关问题

python代码合并链表

在Python中，合并两个已排序的链表（即每个节点包含整数）通常可以通过迭代或递归的方式实现。这里是一个简单的迭代方法：

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

def merge_sorted_lists(l1, l2):
    dummy_node = ListNode(0)  # 创建虚拟头节点
    current = dummy_node  # 当前节点指向虚拟头

    while l1 and l2:  # 只要两个链表都有元素
        if l1.val < l2.val:  # 如果l1的元素小
            current.next = l1  # 将l1的元素添加到结果链表
            l1 = l1.next  # 移动l1到下一个元素
        else:  # 否则，l2的元素小或相等
            current.next = l2  # 将l2的元素添加到结果链表
            l2 = l2.next  # 移动l2到下一个元素

        current = current.next  # 移动current到下一个位置，无论刚才添加的是哪个链表的节点

    # 处理可能剩下的其中一个链表，如果还有剩余，则直接添加
    if l1:
        current.next = l1
    elif l2:
        current.next = l2

    return dummy_node.next  # 返回新的链表头节点

# 示例用法
l1 = ListNode(1, ListNode(2, ListNode(4)))
l2 = ListNode(1, ListNode(3, ListNode(4)))

merged_list = merge_sorted_lists(l1, l2)
while merged_list:
    print(merged_list.val, end=" -> ")
    merged_list = merged_list.next

这个代码首先创建了一个虚拟头节点，然后通过比较当前节点的值将较小的节点添加到结果链表中，并移动指针。最后返回新链表的头节点。

头插法合并有序链表代码

以下是头插法合并有序链表的代码：

ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode* dummy = new ListNode(0);
    ListNode* cur = dummy;
    while (l1 && 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 ? l1 : l2;
    return dummy->next;
}

希望能够帮到你！