聊一聊合并两个排序的链表

前言

思路分析

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

创新互联是一家专业提供高明企业网站建设,专注与网站设计、做网站、html5、小程序制作等业务。10年已为高明众多企业、政府机构等服务。创新互联专业网站制作公司优惠进行中。

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

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

• 如果p1指针指向的节点值比p2指向的值小，合并后的链表节点就取p1节点的值，p1指针继续向前走，进行下一轮的比对。
• 如果p2指针指向的节点值比p1指向的值小，合并后的链表节点就取p2节点的值，p2指针继续向前走，进行下一轮的比对。
• 当p1节点指向null时，合并后的链表节点就为p2所指向的链表节点；当p2节点指向null时，合并后的链表节点就为p1所指向的链表节点。

实现代码

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

• 声明一个函数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);

示例代码

本文所列举的代码，其完整版请移步：

• MergeLinkedList.ts
• MergeLinkedList-test.ts

标题名称：聊一聊合并两个排序的链表
文章链接：http://www.shufengxianlan.com/qtweb/news42/529792.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联