LeetCode 21:合并两个有序链表,简单却不简单

大家好!我是王大神,今天我们来聊一下LeetCode上的一个题目——合并两个有序链表(LeetCode 21)。这个题目看似简单,实则包含了链表操作的多个基础知识点。既然这么有趣,我们就一起来探究一下吧!

题目概述

首先,让我们来看看这个题目到底在说什么。简单来说,这个题目要求你把两个有序的链表合并成一个新的有序链表,并返回新链表的头节点。说人话,就是把两个排好队的人群合并成一个更大的排好队的人群。

为什么要合并有序链表

你可能会问,有序链表合并有什么用呢?其实,在真实的应用场景中,这个技术能帮助我们高效地整合信息和数据。想象一下,两个不同的数据库都有各自排序好的数据,如果我们想整合这两个数据库,合并有序链表就派上用场了。

如何合并?

递归解法

一个简单的方法是使用递归。具体思路是这样的:

  1. 比较两个链表头节点的值。
  2. 选择值较小的节点作为新链表的当前节点。
  3. 递归地合并剩下的节点。

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

迭代解法

除了递归,我们还可以使用迭代来解决这个问题。

  1. 创建一个虚拟头节点。
  2. 用一个指针跟踪新链表的最后一个节点。
  3. 比较两个链表的当前节点,将较小的节点接在新链表后。
  4. 重复以上步骤,直到某个链表为空。

Python代码如下:

def mergeTwoLists(l1: ListNode, l2: ListNode) -> ListNode:
    dummy = ListNode(0)
    current = dummy

    while l1 and l2:
        if l1.val < l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next

    current.next = l1 or l2

    return dummy.next

一句话总结

合并两个有序链表是数据结构中的基础题目,不仅锻炼了我们对链表操作的理解,还让我们见识到了递归和迭代的魅力。

本文由作者 王大神 原创发布于 大神网的AI博客。

转载请注明作者:王大神

原文出处:LeetCode 21:合并两个有序链表,简单却不简单

(0)
打赏 微信扫一扫 微信扫一扫
上一篇 2023年9月25日
下一篇 2023年9月26日