TypeScript合並兩個排序鏈表的方法詳解

Posted on by

前言

給定兩個遞增排序的鏈表，如何將這兩個鏈表合並？合並後的鏈表依然按照遞增排序。本文就跟大傢分享一種解決方案

思路分析

經過前面的學習，我們知道瞭有關鏈表的操作可以用指針來完成。同樣的，這個問題也可以用雙指針的思路來實現：

  • p1指針指向鏈表1的頭節點
  • p2指針指向鏈表2的頭節點

聲明一個變量存儲合並後的鏈表，比對兩個指針指向的節點值大小：

  • 如果p1指針指向的節點值比p2指向的值小，合並後的鏈表節點就取p1節點的值，p1指針繼續向前走，進行下一輪的比對
  • 如果p2指針指向的節點值比p1指向的值小，合並後的鏈表節點就取p2節點的值，p2指針繼續向前走，進行下一輪的比對
  • 當p1節點指向null時，合並後的鏈表節點就為p2所指向的鏈表節點；當p2節點指向null時，合並後的鏈表節點就為p1所指向的鏈表節點。

image-20220627070633451

實現代碼

看完上述分析後，聰明的開發者已經想到代碼怎麼寫瞭。沒錯，這就是典型的遞歸思路，代碼如下：

1.聲明一個函數MergeLinkedList，它接受2個參數：遞增排序的鏈表1，遞增排序的鏈表2

2.遞歸的基線條件：鏈表1為null就返回鏈表2，鏈表2為null就返回鏈表1

3.聲明一個變量pMergedHead用於存儲合並後的鏈表頭節點

4.如果當前鏈表1的節點值小於鏈表2的節點值

  • pMergedHead的值就為鏈表2的節點值
  • pMergedHead的下一個節點值就為鏈表1的下一個節點和鏈表2的節點值比對後的值（遞歸）

5.否則

  • pMergedHead的值就為鏈表1的節點值
  • pMergedHead的下一個節點值就為鏈表2的下一個節點和鏈表1的節點值比對後的值（遞歸）

6.最後，返回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

示例代碼

本文所列舉的代碼如下

MergeLinkedList.ts

import { ListNode } from "./utils/linked-list-models.ts";

/**
 * 合並兩個排序的鏈表
 *  1. p1指針指向鏈表1，p2指針指向鏈表2
 *  2. 遞歸比對指針指向的兩個值，構造新的鏈表
 * @param firstListHead 鏈表1
 * @param secondListHead 鏈表2
 * @constructor
 */
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;
}

MergeLinkedList-test.ts

import { MergeLinkedList } from "../MergeLinkedList.ts";
import LinkedList from "../lib/LinkedList.ts";

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);

到此這篇關於TypeScript合並兩個排序鏈表的方法詳解的文章就介紹到這瞭,更多相關TypeScript合並排序鏈表內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：