1. 题目描述
输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的。
2. 思路分析
准备一个指针node
,假设指向两个链表的中节点的指针分别是:p1
和p2
。
- 比较
p1
和p2
的value
大小
- 如果,p1.value 小于 p2.value, node.next 指向 p1, p1 向后移动
- 否则,node.next 指向 p2, p2 向后移动
- 重复第 1 步,直到其中一个链表遍历完
- 跳出循环,将 node.next 指向未遍历完的链表的剩余部分
整个过程的时间复杂度是 O(N), 空间复杂度是 O(1)
3. 代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
|
class Node { constructor(value = null, next = null) { this.value = value this.next = next } }
function merge(p1, p2) { if (!p1) { return p2 } else if (!p2) { return p1 }
let head = new Node(), node = head
while (p1 && p2) { if (p1.value < p2.value) { node.next = p1 p1 = p1.next } else { node.next = p2 p2 = p2.next }
node = node.next }
if (!p1) { node.next = p2 }
if (!p2) { node.next = p1 }
return head.next }
let list1 = new Node(1, new Node(3, new Node(5, new Node(7, null)))) let list2 = new Node(2, new Node(4, new Node(6, new Node(8, null))))
let head = merge(list1, list2) while (head) { console.log(head.value) head = head.next }
|