AlgoViz Lab交互式算法学习Algorithms first
合并两个有序链表 · 交互式算法学习
合并两条升序链表。
#21 · 链表
合并两个有序链表
Merge Two Sorted Lists
list1 = [1,2,4], list2 = [1,3,4]链表3 个关键状态
步骤 1两个头节点都是 1，取 list1。
tail=11next
→1next
→2next
→3next
→4next
→4next
推荐
双指针复用节点
时间
O(m+n)空间 O(1)每次摘下较小头节点接到结果尾部。
1function mergeTwoLists(a, b) {2 const d = {3 next: null4 };5 let p = d;6 while (a && b) {7 if (a.val <= b.val) {8 p.next = a;9 a = a.next10 } else {11 p.next = b;12 b = b.next13 }14 p = p.next;15 }16 p.next = a || b;17 return d.next;18}多语言参考
来源 · CC BY-SA 4.0 ↗Java · C++ · Go
这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。
1/**2 * Definition for singly-linked list.3 * public class ListNode {4 * int val;5 * ListNode next;6 * ListNode() {}7 * ListNode(int val) { this.val = val; }8 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12 public ListNode mergeTwoLists(ListNode list1, ListNode list2) {13 if (list1 == null) {14 return list2;15 }16 if (list2 == null) {17 return list1;18 }19 if (list1.val <= list2.val) {20 list1.next = mergeTwoLists(list1.next, list2);21 return list1;22 } else {23 list2.next = mergeTwoLists(list1, list2.next);24 return list2;25 }26 }27}交互式算法学习
从执行步骤真正理解 LeetCode 经典 150
本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。
AlgoViz Lab
合并两个有序链表 · 解法对比
合并两条升序链表。
- 测试用例
list1 = [1,2,4], list2 = [1,3,4]- 题目分类
- 链表
- 解法对比
- 2
收集值后排序
把两条链表值收集、排序，再创建新链表。
- 时间
O(n log n)- 空间
O(n)
双指针复用节点
每次摘下较小头节点接到结果尾部。
- 时间
O(m+n)- 空间
O(1)