侧边栏壁纸
博主头像
神奇的程序员

今天的努力只为未来

  • 累计撰写 143 篇文章
  • 累计创建 25 个标签
  • 累计收到 48 条评论

目 录CONTENT

文章目录

合并两个排序的链表

神奇的程序员
2022-06-27 / 1 评论 / 8 点赞 / 301 阅读 / 1,834 字 正在检测是否收录...

前言

给定两个递增排序的链表,如何将这两个链表合并?合并后的链表依然按照递增排序。本文就跟大家分享一种解决方案,欢迎各位感兴趣的开发者阅读本文。

思路分析

经过前面的学习,我们知道了有关链表的操作可以用指针来完成。同样的,这个问题也可以用双指针的思路来实现:

  • p1指针指向链表1的头节点
  • p2指针指向链表2的头节点

声明一个变量存储合并后的链表,比对两个指针指向的节点值大小:

  • 如果p1指针指向的节点值比p2指向的值小,合并后的链表节点就取p1节点的值,p1指针继续向前走,进行下一轮的比对

  • 如果p2指针指向的节点值比p1指向的值小,合并后的链表节点就取p2节点的值,p2指针继续向前走,进行下一轮的比对

  • 当p1节点指向null时,合并后的链表节点就为p2所指向的链表节点;当p2节点指向null时,合并后的链表节点就为p1所指向的链表节点。

    image-20220627070633451

实现代码

看完上述分析后,聪明的开发者已经想到代码怎么写了。没错,这就是典型的递归思路,代码如下:

  • 声明一个函数MergeLinkedList,它接受2个参数:递增排序的链表1,递增排序的链表2
  • 递归的基线条件:链表1为null就返回链表2,链表2为null就返回链表1
  • 声明一个变量pMergedHead用于存储合并后的链表头节点
  • 如果当前链表1的节点值小于链表2的节点值
    • pMergedHead的值就为链表2的节点值
    • pMergedHead的下一个节点值就为链表1的下一个节点和链表2的节点值比对后的值(递归)
  • 否则
    • pMergedHead的值就为链表1的节点值
    • pMergedHead的下一个节点值就为链表2的下一个节点和链表1的节点值比对后的值(递归)
  • 最后,返回pMergedHead
export function MergeLinkedList(
  firstListHead: ListNode | null,
  secondListHead: ListNode | null
): ListNode | null {
  // 基线条件
  if (firstListHead == null) {
    return secondListHead;
  }
  if (secondListHead == null) {
    return firstListHead;
  }
  let pMergedHead: ListNode | null = null;
  if (firstListHead.element < secondListHead.element) {
    pMergedHead = firstListHead;
    pMergedHead.next = MergeLinkedList(firstListHead.next, secondListHead);
  } else {
    pMergedHead = secondListHead;
    pMergedHead.next = MergeLinkedList(firstListHead, secondListHead.next);
  }
  return pMergedHead;
}

测试用例

接下来,我们用思路分析章节中的例子来测试下我们的代码能否正常执行。

const firstLinkedList = new LinkedList();
firstLinkedList.push(1);
firstLinkedList.push(3);
firstLinkedList.push(5);
firstLinkedList.push(7);
firstLinkedList.push(9);
const secondLinkedList = new LinkedList();
secondLinkedList.push(2);
secondLinkedList.push(4);
secondLinkedList.push(6);
secondLinkedList.push(8);

const resultListHead = MergeLinkedList(
  firstLinkedList.getHead(),
  secondLinkedList.getHead()
);

console.log(resultListHead);

image-20220627072844184

示例代码

本文所列举的代码,其完整版请移步👇:

写在最后

至此,文章就分享完毕了。

我是神奇的程序员,一位前端开发工程师。

如果你对我感兴趣,请移步我的个人网站,进一步了解。

  • 文中如有错误,欢迎在评论区指正,如果这篇文章帮到了你,欢迎点赞和关注😊
  • 本文首发于神奇的程序员公众号,未经许可禁止转载💌
8

评论区