当前位置： 首页 > news >正文

用100道题拿下你的算法面试（链表篇-3）：合并两个有序链表

news 2026/4/30 14:04:54

一、面试问题

给定两个有序链表的头节点，将它们合并为一个有序链表，并返回合并后链表的头节点。

示例 1：

输入：

输出：2 -> 3 -> 5 -> 10 -> 15 -> 20 -> 40。

解释：将两个有序链表[5, 10, 15, 40]和[2, 3, 20]按顺序合并，得到：2 -> 3 -> 5 -> 10 -> 15 -> 20 -> 40。

示例 2：

输入：

输出：1 -> 1 -> 2 -> 4。

解释：将有序链表[1 ,1]与[2, 4]合并，结果为：1 -> 1 -> 2 -> 4。

二、【朴素解法】借助数组实现 - 时间复杂度 O ((n+m) × log (n+m))，空间复杂度 O (n+m)

(一) 解法思路

思路：用一个数组存储两条链表的所有节点数值，对数组排序，再根据数组元素重新构建一条有序的结果链表。

(二) 使用 5 种语言实现

1. C++

#include <iostream> #include <vector> #include <algorithm> using namespace std; class Node { public: int data; Node *next; Node(int x) { data = x; next = nullptr; } }; Node *sortedMerge(Node *head1, Node *head2) { vector<int> arr; // 存入第一个链表的节点值 while (head1 != nullptr) { arr.push_back(head1->data); head1 = head1->next; } // 存入第二个链表的节点值 while (head2 != nullptr) { arr.push_back(head2->data); head2 = head2->next; } // 对数组进行排序 sort(arr.begin(), arr.end()); // 用排序后的值创建新链表 Node *dummy = new Node(-1); Node *curr = dummy; for (int i = 0; i < arr.size(); i++) { curr->next = new Node(arr[i]); curr = curr->next; } return dummy->next; } void printList(Node *curr) { while (curr != nullptr) { cout << curr->data; if (curr->next != nullptr) cout << " -> "; curr = curr->next; } cout << endl; } int main() { Node *head1 = new Node(5); head1->next = new Node(10); head1->next->next = new Node(15); head1->next->next->next = new Node(40); Node *head2 = new Node(2); head2->next = new Node(3); head2->next->next = new Node(20); Node *res = sortedMerge(head1, head2); printList(res); return 0; }

2. Java

import java.util.ArrayList; import java.util.Collections; class Node { int data; Node next; Node(int x) { data = x; next = null; } } class DSA { static Node sortedMerge(Node head1, Node head2) { ArrayList<Integer> arr = new ArrayList<>(); // 存入第一个链表的节点值 while (head1 != null) { arr.add(head1.data); head1 = head1.next; } // 存入第二个链表的节点值 while (head2 != null) { arr.add(head2.data); head2 = head2.next; } // 对列表进行排序 Collections.sort(arr); // 用排序后的值创建新链表 Node dummy = new Node(-1); Node curr = dummy; for (int i = 0; i < arr.size(); i++) { curr.next = new Node(arr.get(i)); curr = curr.next; } return dummy.next; } static void printList(Node curr) { while (curr != null) { System.out.print(curr.data); if (curr.next != null) { System.out.print(" -> "); } curr = curr.next; } System.out.println(); } public static void main(String[] args) { Node head1 = new Node(5); head1.next = new Node(10); head1.next.next = new Node(15); head1.next.next.next = new Node(40); Node head2 = new Node(2); head2.next = new Node(3); head2.next.next = new Node(20); Node res = sortedMerge(head1, head2); printList(res); } }

3. Python

class Node: def __init__(self, x): self.data = x self.next = None def sortedMerge(head1, head2): arr = [] # 存入第一个链表的节点值 while head1 is not None: arr.append(head1.data) head1 = head1.next # 存入第二个链表的节点值 while head2 is not None: arr.append(head2.data) head2 = head2.next # 对列表进行排序 arr.sort() # 用排序后的值创建新链表 dummy = Node(-1) curr = dummy for value in arr: curr.next = Node(value) curr = curr.next return dummy.next def printList(node): while node is not None: print(f"{node.data}", end="") if node.next is not None: print(" -> ", end="") node = node.next print() if __name__ == "__main__": head1 = Node(5) head1.next = Node(10) head1.next.next = Node(15) head1.next.next.next = Node(40) head2 = Node(2) head2.next = Node(3) head2.next.next = Node(20) res = sortedMerge(head1, head2) printList(res)

4. C#

using System; using System.Collections.Generic; class Node { public int data; public Node next; public Node(int x) { data = x; next = null; } } class DSA { static Node sortedMerge(Node head1, Node head2) { List<int> arr = new List<int>(); // 存入第一个链表的节点值 while (head1 != null) { arr.Add(head1.data); head1 = head1.next; } // 存入第二个链表的节点值 while (head2 != null) { arr.Add(head2.data); head2 = head2.next; } // 对列表进行排序 arr.Sort(); // 用排序后的值创建新链表 Node dummy = new Node(-1); Node curr = dummy; foreach(int value in arr) { curr.next = new Node(value); curr = curr.next; } return dummy.next; } static void printList(Node curr) { while (curr != null) { Console.Write(curr.data); if (curr.next != null) { Console.Write(" -> "); } curr = curr.next; } Console.WriteLine(); } static void Main(string[] args) { Node head1 = new Node(5); head1.next = new Node(10); head1.next.next = new Node(15); head1.next.next.next = new Node(40); Node head2 = new Node(2); head2.next = new Node(3); head2.next.next = new Node(20); Node res = sortedMerge(head1, head2); printList(res); } }

5. JavaScript

class Node { constructor(x) { this.data = x; this.next = null; } } function sortedMerge(head1, head2) { let arr = []; // 存入第一个链表的节点值 while (head1 !== null) { arr.push(head1.data); head1 = head1.next; } // 存入第二个链表的节点值 while (head2 !== null) { arr.push(head2.data); head2 = head2.next; } // 对数组进行排序 arr.sort((x, y) => x - y); // 用排序后的值创建新链表 let dummy = new Node(-1); let curr = dummy; for (let value of arr) { curr.next = new Node(value); curr = curr.next; } return dummy.next; } function printList(node) { while (node !== null) { process.stdout.write(node.data.toString()); if (node.next !== null) { process.stdout.write(" -> "); } node = node.next; } } let head1 = new Node(5); head1.next = new Node(10); head1.next.next = new Node(15); head1.next.next.next = new Node(40); let head2 = new Node(2); head2.next = new Node(3); head2.next.next = new Node(20); let res = sortedMerge(head1, head2); printList(res);

(三)代码输出和算法复杂度

输出：

2 -> 3 -> 5 -> 10 -> 15 -> 20 -> 40

时间复杂度：O ((n+m) × log (n+m))

空间复杂度：O (n+m)

三、【优化解法】使用递归合并 - 时间复杂度 O (n+m)，空间复杂度 O (n+m)

(一) 解法思路

核心思路：每次选取值更小的头节点，然后通过递归合并剩余部分。如果其中一个链表为空，直接返回另一个；否则，将较小的节点作为合并链表的下一个节点，它的 next 指向剩余部分的递归合并结果。

算法：

  • 如果 head1 为空，返回 head2。
  • 如果 head2 为空，返回 head1。
  • 比较 head1.data 和 head2.data。
  • 如果：

head1.data <= head2.data：

=> 将 head 设为 head1

=> 将 head.next 设为 merge (head1.next, head2)

否则：

=> 将 head 设为 head2

=> 将 head.next 设为 merge (head1, head2.next)

  • 返回 head。

(二) 使用 6 种语言实现

1. C++

#include <iostream> using namespace std; class Node { public: int data; Node* next; Node(int x) { data = x; next = nullptr; } }; Node* sortedMerge(Node* head1, Node* head2) { // 基本情况 if (head1 == nullptr) return head2; if (head2 == nullptr) return head1; // 根据较小的值进行递归合并 if (head1->data <= head2->data) { head1->next = sortedMerge(head1->next, head2); return head1; } else { head2->next = sortedMerge(head1, head2->next); return head2; } } void printList(Node* curr) { while (curr != nullptr) { cout << curr->data; if (curr->next != nullptr) cout << " -> "; curr = curr->next; } cout << endl; } int main() { Node* head1 = new Node(5); head1->next = new Node(10); head1->next->next = new Node(15); head1->next->next->next = new Node(40); Node* head2 = new Node(2); head2->next = new Node(3); head2->next->next = new Node(20); Node* res = sortedMerge(head1, head2); printList(res); return 0; }

2. C

#include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node *next; }; struct Node *sortedMerge(struct Node *head1, struct Node *head2) { // 基准情况 if (head1 == NULL) return head2; if (head2 == NULL) return head1; // 根据较小的值进行递归合并 if (head1->data <= head2->data) { head1->next = sortedMerge(head1->next, head2); return head1; } else { head2->next = sortedMerge(head1, head2->next); return head2; } } void printList(struct Node *curr) { while (curr != NULL) { printf("%d", curr->data); if (curr->next != NULL) { printf(" -> "); } curr = curr->next; } printf("\n"); } struct Node *createNode(int data) { struct Node *newNode = (struct Node *)malloc(sizeof(struct Node)); newNode->data = data; newNode->next = NULL; return newNode; } int main() { struct Node *head1 = createNode(5); head1->next = createNode(10); head1->next->next = createNode(15); head1->next->next->next = createNode(40); struct Node *head2 = createNode(2); head2->next = createNode(3); head2->next->next = createNode(20); struct Node *res = sortedMerge(head1, head2); printList(res); return 0; }

3. Java

class Node { int data; Node next; Node(int x) { data = x; next = null; } } class DSA { static Node sortedMerge(Node head1, Node head2) { // 基准情况 if (head1 == null) return head2; if (head2 == null) return head1; // 根据较小的值进行递归合并 if (head1.data <= head2.data) { head1.next = sortedMerge(head1.next, head2); return head1; } else { head2.next = sortedMerge(head1, head2.next); return head2; } } static void printList(Node curr) { while (curr != null) { System.out.print(curr.data); if (curr.next != null) System.out.print(" -> "); curr = curr.next; } System.out.println(); } public static void main(String[] args) { Node head1 = new Node(5); head1.next = new Node(10); head1.next.next = new Node(15); head1.next.next.next = new Node(40); Node head2 = new Node(2); head2.next = new Node(3); head2.next.next = new Node(20); Node res = sortedMerge(head1, head2); printList(res); } }

4. Python

class Node: def __init__(self, x): self.data = x self.next = None def sortedMerge(head1, head2): # 基准情况 if head1 is None: return head2 if head2 is None: return head1 # 根据较小的值进行递归合并 if head1.data <= head2.data: head1.next = sortedMerge(head1.next, head2) return head1 else: head2.next = sortedMerge(head1, head2.next) return head2 def printList(node): while node is not None: print(f"{node.data}", end="") if node.next is not None: print(" -> ", end="") node = node.next print() if __name__ == "__main__": head1 = Node(5) head1.next = Node(10) head1.next.next = Node(15) head1.next.next.next = Node(40) head2 = Node(2) head2.next = Node(3) head2.next.next = Node(20) res = sortedMerge(head1, head2) printList(res)

5. C#

using System; class Node { public int data; public Node next; public Node(int x) { data = x; next = null; } } class DSA { static Node sortedMerge(Node head1, Node head2) { // 基准情况 if (head1 == null) return head2; if (head2 == null) return head1; // 根据较小的值进行递归合并 if (head1.data <= head2.data) { head1.next = sortedMerge(head1.next, head2); return head1; } else { head2.next = sortedMerge(head1, head2.next); return head2; } } static void printList(Node curr) { while (curr != null) { Console.Write(curr.data); if (curr.next != null) Console.Write(" -> "); curr = curr.next; } Console.WriteLine(); } static void Main(string[] args) { Node head1 = new Node(5); head1.next = new Node(10); head1.next.next = new Node(15); head1.next.next.next = new Node(40); Node head2 = new Node(2); head2.next = new Node(3); head2.next.next = new Node(20); Node res = sortedMerge(head1, head2); printList(res); } }

6. JavaScript

class Node { constructor(x) { this.data = x; this.next = null; } } function sortedMerge(head1, head2) { // 基准情况 if (head1 === null) return head2; if (head2 === null) return head1; // 根据较小的值进行递归合并 if (head1.data <= head2.data) { head1.next = sortedMerge(head1.next, head2); return head1; } else { head2.next = sortedMerge(head1, head2.next); return head2; } } function printList(node) { while (node !== null) { process.stdout.write(node.data.toString()); if (node.next !== null) { process.stdout.write(" -> "); } node = node.next; } } // 测试代码 let head1 = new Node(5); head1.next = new Node(10); head1.next.next = new Node(15); head1.next.next.next = new Node(40); let head2 = new Node(2); head2.next = new Node(3); head2.next.next = new Node(20); let res = sortedMerge(head1, head2); printList(res);

(三)代码输出和算法复杂度

输出：

2 -> 3 -> 5 -> 10 -> 15 -> 20 -> 40

时间复杂度：O (n+m)

空间复杂度：O (n+m)

四、【高效解法】使用迭代合并 - 时间复杂度 O (n+m)，空间复杂度 O (1)

(一) 解法思路

核心思路：借助哑节点（dummy node）简化流程，迭代合并两个有序链表。用一个当前指针追踪合并链表的最后一个节点，依次比较两个链表的节点，把更小的节点拼接到合并链表后。当其中一个链表遍历完毕，直接把另一个链表的剩余节点拼接上去。最终返回哑节点的下一个节点，即为合并后的链表头。

工作原理：

(二) 使用 6 种语言实现

1. C++

#include <iostream> using namespace std; class Node { public: int data; Node* next; Node(int x) { data = x; next = nullptr; } }; Node* sortedMerge(Node* head1, Node* head2) { // 创建一个哑节点以简化合并过程 Node* dummy = new Node(-1); Node* curr = dummy; // 遍历两个链表 while (head1 != nullptr && head2 != nullptr) { // 将较小的节点加入合并后的链表 if (head1->data <= head2->data) { curr->next = head1; head1 = head1->next; } else { curr->next = head2; head2 = head2->next; } curr = curr->next; } // 如果还有剩余链表，直接拼接在末尾 if (head1 != nullptr) { curr->next = head1; } else { curr->next = head2; } // 返回从哑节点下一个节点开始的合并链表 return dummy->next; } void printList(Node* head) { while (head != nullptr) { cout << head->data; if (head->next != nullptr) cout << " -> "; head = head->next; } cout << endl; } int main() { Node* head1 = new Node(5); head1->next = new Node(10); head1->next->next = new Node(15); head1->next->next->next = new Node(40); Node* head2 = new Node(2); head2->next = new Node(3); head2->next->next = new Node(20); Node* res = sortedMerge(head1, head2); printList(res); return 0; }

2. C

#include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node* next; }; struct Node* createNode(int data); struct Node* sortedMerge(struct Node* head1, struct Node* head2) { // 创建一个哑节点以简化合并过程 struct Node* dummy = createNode(-1); struct Node* curr = dummy; // 遍历两个链表 while (head1 != NULL && head2 != NULL) { // 将较小的节点加入合并后的链表 if (head1->data <= head2->data) { curr->next = head1; head1 = head1->next; } else { curr->next = head2; head2 = head2->next; } curr = curr->next; } // 如果还有剩余链表，直接拼接在末尾 if (head1 != NULL) { curr->next = head1; } else { curr->next = head2; } // 返回从哑节点下一个节点开始的合并链表 return dummy->next; } void printList(struct Node* head) { while (head != NULL) { printf("%d", head->data); if (head->next != NULL) { printf(" -> "); } head = head->next; } printf("\n"); } struct Node* createNode(int data) { struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); newNode->data = data; newNode->next = NULL; return newNode; } int main() { struct Node* head1 = createNode(5); head1->next = createNode(10); head1->next->next = createNode(15); head1->next->next->next = createNode(40); struct Node* head2 = createNode(2); head2->next = createNode(3); head2->next->next = createNode(20); struct Node* res = sortedMerge(head1, head2); printList(res); return 0; }

3. Java

class Node { int data; Node next; Node(int x) { data = x; next = null; } } class DSA { static Node sortedMerge(Node head1, Node head2) { // 创建一个哑节点以简化合并过程 Node dummy = new Node(-1); Node curr = dummy; // 遍历两个链表 while (head1 != null && head2 != null) { // 将较小的节点加入合并后的链表 if (head1.data <= head2.data) { curr.next = head1; head1 = head1.next; } else { curr.next = head2; head2 = head2.next; } curr = curr.next; } // 如果还有剩余链表，直接拼接在末尾 if (head1 != null) { curr.next = head1; } else { curr.next = head2; } // 返回从哑节点下一个节点开始的合并链表 return dummy.next; } static void printList(Node head) { while (head != null) { System.out.print(head.data); if (head.next != null) System.out.print(" -> "); head = head.next; } System.out.println(); } public static void main(String[] args) { Node head1 = new Node(5); head1.next = new Node(10); head1.next.next = new Node(15); head1.next.next.next = new Node(40); Node head2 = new Node(2); head2.next = new Node(3); head2.next.next = new Node(20); Node res = sortedMerge(head1, head2); printList(res); } }

4. Python

class Node: def __init__(self, x): self.data = x self.next = None def sortedMerge(head1, head2): # 创建一个哑节点以简化合并过程 dummy = Node(-1) curr = dummy # 遍历两个链表 while head1 is not None and head2 is not None: # 将较小的节点加入合并后的链表 if head1.data <= head2.data: curr.next = head1 head1 = head1.next else: curr.next = head2 head2 = head2.next curr = curr.next # 如果还有剩余链表，直接拼接在末尾 if head1 is not None: curr.next = head1 else: curr.next = head2 # 返回从哑节点下一个节点开始的合并链表 return dummy.next def printList(head): while head is not None: if head.next is not None: print(head.data, end=" -> ") else: print(head.data) head = head.next if __name__ == "__main__": head1 = Node(5) head1.next = Node(10) head1.next.next = Node(15) head1.next.next.next = Node(40) head2 = Node(2) head2.next = Node(3) head2.next.next = Node(20) res = sortedMerge(head1, head2) printList(res)

5. C#

using System; class Node { public int data; public Node next; public Node(int x) { data = x; next = null; } } class DSA { static Node sortedMerge(Node head1, Node head2) { // 创建一个哑节点以简化合并过程 Node dummy = new Node(-1); Node curr = dummy; // 遍历两个链表 while (head1 != null && head2 != null) { // 将较小的节点加入合并后的链表 if (head1.data <= head2.data) { curr.next = head1; head1 = head1.next; } else { curr.next = head2; head2 = head2.next; } curr = curr.next; } // 如果还有剩余链表，直接拼接在末尾 if (head1 != null) { curr.next = head1; } else { curr.next = head2; } // 返回从哑节点下一个节点开始的合并链表 return dummy.next; } static void printList(Node head) { while (head != null) { Console.Write(head.data); if (head.next != null) Console.Write(" -> "); head = head.next; } Console.WriteLine(); } static void Main(string[] args) { Node head1 = new Node(5); head1.next = new Node(10); head1.next.next = new Node(15); head1.next.next.next = new Node(40); Node head2 = new Node(2); head2.next = new Node(3); head2.next.next = new Node(20); Node res = sortedMerge(head1, head2); printList(res); } }

6. JavaScript

class Node { constructor(x) { this.data = x; this.next = null; } } function sortedMerge(head1, head2) { // 创建一个哑节点以简化合并过程 let dummy = new Node(-1); let curr = dummy; // 遍历两个链表 while (head1 !== null && head2 !== null) { // 将较小的节点加入合并后的链表 if (head1.data <= head2.data) { curr.next = head1; head1 = head1.next; } else { curr.next = head2; head2 = head2.next; } curr = curr.next; } // 如果还有剩余链表，直接拼接在末尾 if (head1 !== null) { curr.next = head1; } else { curr.next = head2; } // 返回从哑节点下一个节点开始的合并链表 return dummy.next; } function printList(head) { let result = ""; while (head !== null) { result += head.data; if (head.next !== null) { result += " -> "; } head = head.next; } console.log(result); } // 测试代码 let head1 = new Node(5); head1.next = new Node(10); head1.next.next = new Node(15); head1.next.next.next = new Node(40); let head2 = new Node(2); head2.next = new Node(3); head2.next.next = new Node(20); let res = sortedMerge(head1, head2); printList(res);

(三)代码输出和算法复杂度

输出：

2 -> 3 -> 5 -> 10 -> 15 -> 20 -> 40

时间复杂度：O (n+m)

空间复杂度：O (1)

http://www.jsqmd.com/news/725610/

相关文章：

  • APK Installer：基于Windows Subsystem for Android的轻量级安卓应用安装架构
  • 研一新生别再傻读文献了！导师都在偷偷用的AI阅读神器，30页英文Paper 30分钟搞定
  • 英雄联盟终极自动化助手：LeagueAkari 免费工具完整指南
  • Element UI单选框样式改造指南：告别默认样式，打造个性化radio和radio-button
  • 城市消费新选择：京东e卡回收正规平台 - 京回收小程序
  • 苏州鼎轩废旧电子产品：相城区口碑好的机房服务器设备回收公司怎么联系 - LYL仔仔
  • 2026最新办公室设计装修/总部大楼设计装修/写字楼设计装修服务商推荐！大湾区优质权威榜单发布，靠谱专业广东省广州等地服务公司推荐 - 十大品牌榜
  • 别再只测吞吐量了！用open62541实测OPC UA的RTT与连接开销（附避坑指南）
  • 2026年武汉短视频代运营与GEO推广深度横评：五大服务商对比选购指南 - 年度推荐企业名录
  • Lan Mouse技术深度解析：跨平台键鼠共享架构剖析
  • 短剧出海翻译避坑指南：我们踩过的5个坑和对应的解法
  • 2026毕设生死线：哪些降重软件可以同时降低查重率和AIGC疑似率？（附实测避坑指南） - nut-king
  • 【AI面试临阵磨枪-31】Agent 反思（Reflection）机制如何实现？作用是什么？
  • send()函数flags参数全解析：从MSG_DONTWAIT到MSG_MORE，如何选对模式提升网络性能？
  • 【案例】金兰功率半导体（无锡） 无锡哲讯智能｜SAP全链路数字化管理，赋能功率半导体模块国产化高质量发展
  • 终极自动化工具配置指南：3步解锁网易云音乐插件生态完整方案
  • 黑龙江省唯力达家政服务：双城有实力的办公室开荒保洁公司有哪些 - LYL仔仔
  • 如何用KMS_VL_ALL_AIO实现Windows和Office永久激活：完整指南
  • 海能达正品价优的核心代理商黑龙江单工科技有限公司为HM780行业应用助力 - 速递信息
  • 2025届学术党必备的六大AI论文助手推荐榜单
  • 在线PH计（PH传感器/变送器）哪个牌子好？2026年主流品牌权威评测与选型推荐 - 陈工日常
  • 2026年GEO优化实战：破解关键词排名痛点，广西头部制造商效果验证
  • 别再手动K帧了！Blender 3.6+ 自动关键帧与插值类型实战避坑指南
  • 2026全球主流外汇平台APP实测对比 合规性与实用性解析 - 速递信息
  • 10分钟终极指南：用Locale-Emulator轻松运行多语言Windows程序
  • 京东e卡闲置贬值？真实回收价格曝光 - 京顺回收
  • 大模型问答优化的技术纵深
  • 2026腾讯企业邮箱怎么开通？最新电话与方式全攻略 - 品牌2025
  • Linux内核WiFi驱动开发入门：手把手拆解cfg80211与mac80211的交互流程
  • 创业公司如何利用 Taotoken 实现低成本多模型 A/B 测试