如何详细解析TypeScript中合并两个有序链表的算法实现？

本文共计1224个文字，预计阅读时间需要5分钟。

目录前言思路分析实现代码测试用例示例代码前言给定两个递增排序的链表，合并这两个链表并保持排序顺序。

思路分析

1.创建一个新链表，用于存放合并后的结果。

2.使用两个指针分别遍历两个链表。

3.比较两个指针指向的节点值，将较小的节点添加到新链表中。

4.移动指针，继续比较下一个节点。

5.当一个链表遍历完成，将另一个链表的剩余部分直接连接到新链表的末尾。

实现代码

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

def merge_sorted_lists(l1, l2): dummy=ListNode() current=dummy while l1 and l2: if l1.val

测试用例python创建测试链表l1=ListNode(1, ListNode(3, ListNode(5)))l2=ListNode(2, ListNode(4, ListNode(6)))

合并链表merged_list=merge_sorted_lists(l1, l2)

打印合并后的链表while merged_list: print(merged_list.val, end= ) merged_list=merged_list.next

示例代码python示例：合并两个链表def print_list(node): while node: print(node.val, end= ) node=node.next

l1=ListNode(1, ListNode(3, ListNode(5)))l2=ListNode(2, ListNode(4, ListNode(6)))

print(List 1: , end=)print_list(l1)print(\nList 2: , end=)print_list(l2)

merged_list=merge_sorted_lists(l1, l2)print(\nMerged List: , end=)print_list(merged_list)

结果：List 1: 1 3 5List 2: 2 4 6Merged List: 1 2 3 4 5 6

目录

• 前言
• 思路分析
• 实现代码
• 测试用例
• 示例代码

前言

给定两个递增排序的链表，如何将这两个链表合并？合并后的链表依然按照递增排序。本文就跟大家分享一种解决方案

思路分析

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

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

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

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

实现代码

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

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

示例代码

本文所列举的代码如下

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合并排序链表内容请搜索自由互联以前的文章或继续浏览下面的相关文章希望大家以后多多支持自由互联！