# 合并链表|博客系列

> 本文介绍如何合并两个有序链表为一个新的有序链表，包含详细的题目描述、解题思路和递归实现代码，适合数据结构与算法学习者参考。

- 原文：https://feinterview.poetries.top/docs/fe-blog-docs/blog-docs/data-struct/21-%E5%90%88%E5%B9%B6%E9%93%BE%E8%A1%A8
- 来源：前端进阶之旅（feinterview.poetries.top）
- 更新：2025.10.25

---

### 题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

例如🌰

```javascript
输入:  1 -> 2 -> 4 和 3 -> 5 -> 6
输出:  1 -> 2 -> 3 -> 4 -> 5 -> 6
```

### 解题思路

1. 从两个链表的头部开始逐步比较, 取较小的节点;
2. 利用递归, 继续比较上一次剩下的链表和上一次较小节点的`next`
3. 需要考虑两个节点为`null`的情况, 取对方节点返回.

### coding

```javascript
/*
* 合并两个链表
* @params {ListNode} l1
* @params {ListNode} l2
* @returns {ListNode}
*/
function MergeList(l1, l2) {
    if (!l1) {
        return l2
    }
    if (!l2) {
        return l1
    }
    let head = null
    if (l1.val < l2.val) {
        head = l1
        head.next = MergeList(l1.next, l2)
    } else {
        head = l2
        head.next = MergeList(l2.next, l1)
    }
    return head
}
```

**测试代码**

```javascript
function ListNode(val) {
    this.val = val
    this.next = null
}

function transformArrayToList(array) {
    let list = new ListNode(null)
    let node = list
    while (array.length > 0) {
        let val = array.pop()
        node.next = new ListNode(val)
        node = node.next
    }
    return list.next
}           
/*
* 合并两个链表
* @params {ListNode} l1
* @params {ListNode} l2
* @returns {ListNode}
*/
function MergeList(l1, l2) {
    if (!l1) {
        return l2
    }
    if (!l2) {
        return l1
    }
    let head = null
    if (l1.val < l2.val) {
        head = l1
        head.next = MergeList(l1.next, l2)
    } else {
        head = l2
        head.next = MergeList(l2.next, l1)
    }
    return head
}

let l1 = transformArrayToList([7, 6, 4, 2])
let l2 = transformArrayToList([8, 5, 3, 1])
console.log(MergeList(l1, l2))
```
