python 单链表的归并算法

单链表的归并算法可以使用递归来实现。具体步骤如下：

1. 如果两个链表中有一个为空，则直接返回另一个链表。
2. 比较两个链表头节点的值，将较小的节点作为合并后链表的头节点。
3. 递归调用归并函数，将较小节点的 next 指针指向剩余节点的合并结果。
4. 返回合并后的链表头节点。

以下是 Python 代码实现：

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

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    if not l1:
        return l2
    if not l2:
        return l1
    if l1.val < l2.val:
        l1.next = mergeTwoLists(l1.next, l2)
        return l1
    else:
        l2.next = mergeTwoLists(l1, l2.next)
        return l2

该函数接受两个单链表作为参数，返回合并后的单链表。

相关问题

单链表排序算法从小到大

单链表排序算法可以采用插入排序或归并排序，这里给出一个基于插入排序的示例代码：

def insert_sort(head):
    if not head or not head.next:
        return head
    
    dummy = ListNode(0)  # 创建一个辅助节点
    pre = dummy
    cur = head
    
    while cur:
        next_node = cur.next  # 记录下一个节点
        # 找到插入位置
        while pre.next and pre.next.val < cur.val:
            pre = pre.next
        # 插入节点
        cur.next = pre.next
        pre.next = cur
        pre = dummy  # 重置pre指针
        cur = next_node  # 处理下一个节点

    return dummy.next

算法思路：

1. 创建一个辅助节点dummy，将其指向head。
2. 定义两个指针pre和cur，初始时pre指向dummy，cur指向head。
3. 遍历链表，对于每个节点cur，记录其下一个节点next_node，然后在已排序的链表中找到插入位置，并将其插入。
4. 重置pre指针为dummy，cur指针为next_node，继续遍历链表，直到所有节点都被插入。
5. 返回dummy.next作为排序后的链表头节点。

时间复杂度为O(n^2)，空间复杂度为O(1)。如果要优化时间复杂度，可以采用归并排序等高效算法。

python 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值升序排列的单链表。

可以使用双指针法，从两个单链表的头节点开始比较，将较小的节点依次添加到新的单链表中，直到其中一个单链表为空，然后将另一个单链表的剩余部分直接添加到新单链表的末尾。

具体实现如下：

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)  # 创建一个虚拟头节点
    cur = dummy  # cur 指向新链表的最后一个节点

    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

    # 将剩余的节点直接添加到新链表的末尾
    if l1:
        cur.next = l1
    if l2:
        cur.next = l2

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

测试代码：

# 创建两个有序链表
l1 = ListNode(1, ListNode(2, ListNode(4)))
l2 = ListNode(1, ListNode(3, ListNode(4)))

# 将两个链表合并
merged_list = mergeTwoLists(l1, l2)

# 输出合并后的链表
while merged_list:
    print(merged_list.val, end=' ')
    merged_list = merged_list.next

输出结果：`1 1 2 3 4 4`