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

张

张建站

2026/4/30 14:00:44

10分钟阅读

一、面试问题给定两个有序链表的头节点将它们合并为一个有序链表并返回合并后链表的头节点。示例 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 ((nm) × log (nm))空间复杂度 O (nm)(一) 解法思路思路用一个数组存储两条链表的所有节点数值对数组排序再根据数组元素重新构建一条有序的结果链表。(二) 使用 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) { vectorint 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. Javaimport 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) { ArrayListInteger 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. Pythonclass 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) { Listint arr new Listint(); // 存入第一个链表的节点值 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. JavaScriptclass 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 ((nm) × log (nm))空间复杂度O (nm)三、【优化解法】使用递归合并 - 时间复杂度 O (nm)空间复杂度 O (nm)(一) 解法思路核心思路每次选取值更小的头节点然后通过递归合并剩余部分。如果其中一个链表为空直接返回另一个否则将较小的节点作为合并链表的下一个节点它的 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. Javaclass 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. Pythonclass 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. JavaScriptclass 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 (nm)空间复杂度O (nm)四、【高效解法】使用迭代合并 - 时间复杂度 O (nm)空间复杂度 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. Javaclass 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. Pythonclass 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. JavaScriptclass 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 (nm)空间复杂度O (1)