单链表合并

单链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。当两个已排序的单链表需要合并时，可以使用以下步骤：

1. 创建一个新的空链表，用于存储合并后的结果。
2. 遍历两个链表，比较当前节点的值，将较小的节点添加到新链表中。
3. 继续遍历下一个节点，重复步骤2，直到其中一个链表遍历完毕。
4. 将剩余的链表添加到新链表的末尾。

以下是使用Python实现单链表合并的示例代码：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def mergeTwoLists(l1, l2):
    # 创建一个新链表用于存储结果
    dummy = ListNode(0)
    curr = dummy
    while l1 and l2:
        if l1.val < l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
    # 将剩余的链表添加到新链表的末尾
    if l1:
        curr.next = l1
    elif l2:
        curr.next = l2
    return dummy.next

在上面的代码中，我们首先定义了一个ListNode类来表示单链表中的节点。然后，我们定义了mergeTwoLists函数来合并两个已排序的单链表。该函数使用一个循环来比较两个链表的当前节点值，将较小的节点添加到新链表中，并继续遍历下一个节点，直到其中一个链表遍历完毕。最后，我们将剩余的链表添加到新链表的末尾，并返回新链表的头节点。

请注意，上述代码假设输入的两个单链表已经按照升序排序。如果输入的单链表未排序，则需要在合并之前先对它们进行排序。此外，由于单链表的合并时间复杂度为O(n)，其中n是两个链表中节点的总数，因此该算法在实际应用中是高效的。