# 合并两个有序链表
# 1、题目描述
输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的。
# 2、思路
首先需要判断几个特殊情况,即判断输入的两个指针是否为空。如果第一个链表为空,则直接返回第二个链表;如果第二个链表为空,则直接返回第一个链表。如果两个链表都是空链表,合并的结果是得到一个空链表。
两个链表都是排序好的,我们只需要从头遍历链表,判断当前指针,哪个链表中的值小,即赋给合并链表指针,剩余的结点仍然是排序的,所以合并的步骤和之前是一样的,所以这是典型的递归过程,用递归可以轻松实现。
# Johninch
- 递归:
function merge(p1, p2) {
if (!p1 || !p2) {
return p1 || p2
}
let head = null // 头节点
if (p1.value < p2.value) {
head = p1
head.next = merge(p1.next, p2)
} else {
head = p2
head.next = merge(p1, p2.next)
}
return head
}
- 非递归:
function merge(p1, p2) {
if (!p1 || !p2) {
return p1 || p2
}
let head = new Node() // 增加头节点
let 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 = p1
}
if (p2) {
node.next = p2
}
return head.next;
}
# Caleb
function mergeList(head1, head2) {
if(head1 === null || head2 === null){
return head1 || head2
}
const head = null;
if(head1.val <= head2.val){
head = head1;
head.next = mergeList(head1.next, head2)
}else{
head = head2;
head.next = mergeList(head1, head2.next)
}
}