首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

我正在尝试以升序将两个链表合并为1个链表

将两个链表合并为一个链表的算法可以使用迭代或递归方法。

方法1:迭代 迭代方法通过比较两个链表的节点值,将较小的节点依次加入到新链表中。具体步骤如下:

  1. 创建一个新的链表作为结果链表的头部,以及一个指针指向当前结果链表的末尾。
  2. 初始化两个指针分别指向两个链表的头部。
  3. 进行循环,直到两个链表都遍历完: 1)比较两个链表当前节点的值,将较小的节点加入到结果链表中。 2)更新指针,将当前节点后移。
  4. 如果其中一个链表已经遍历完,将另一个链表剩余的节点直接加入到结果链表中。
  5. 返回结果链表。

具体代码如下(使用Python语言):

代码语言:txt
复制
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    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

    # 将剩余的链表连接到结果链表的末尾
    curr.next = l1 if l1 else l2

    return dummy.next  # 返回结果链表的头部

方法2:递归 递归方法通过不断比较两个链表的头节点,将较小的节点加入到结果链表中,并递归地处理剩下的节点。具体步骤如下:

  1. 如果其中一个链表为空,直接返回另一个链表作为结果。
  2. 比较两个链表的头节点的值,将较小的节点作为结果链表的头节点。
  3. 递归调用合并函数,将较小节点的下一个节点与另一个链表进行合并,并将结果连接到较小节点的下一个节点。
  4. 返回结果链表的头节点。

具体代码如下(使用Python语言):

代码语言:txt
复制
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

这两种方法都可以实现将两个链表合并为一个链表的功能。它们的时间复杂度都是O(n + m),其中n和m分别为两个链表的长度。

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

  • 领券