首页
后端开发
C
LeetCode归并两个链表|Merge Two Sorted Lists

LeetCode归并两个链表|Merge Two Sorted Lists

14 次浏览 0 条评论
cpp
cpp

归并两个链表

对于归并两个链表的问题，下面是解决方案。我们可以通过以下步骤来将两个已排序的链表合并成一个新的有序链表。

  1. 初始化一个虚拟头节点，用于简化代码。
  2. 比较两个链表的节点值，将较小的节点加入新链表。
  3. 继续遍历两个链表，直到其中一个链表为空。
  4. 将剩余的链表直接连接到新链表，因为该链表已经是有序的。
  5. 返回新链表的头节点（即虚拟头节点的next）。

示例代码（Python）：

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

def mergeTwoLists(l1, l2):
    dummy = ListNode()  # 虚拟头节点
    current = dummy

    while l1 and l2:
        if l1.val < l2 xss=removed xss=removed xss=removed xss=removed xss=removed xss=removed>

解析

归并两个链表的核心思想是不断比较两个链表的节点，直到全部节点合并到新的链表中。关键在于如何管理指针的移动以及如何处理剩余节点。

这个方法的时间复杂度为O(n)，其中n是两个链表总节点数。

总结

这道题目考察了对链表指针操作的掌握，适合初学者练习链表相关问题，尤其是如何进行链表合并和如何简化代码。
cpp 文件大小：1.35KB