综合文章

# 题目描述

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

例如🌰

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

# 解题思路

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

# coding

/*
* 合并两个链表
* @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
}

测试代码

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))
阅读全文

← 链表倒数第k个节点 →