合并两个排好序的链表

题目描述

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

数据范围： 0≤n≤1000，-1000≤ 节点值 ≤ 1000 要求：空间复杂度 O(1)，时间复杂度 O(n)

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：

或输入{-1,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：

示例

示例1

输入： {1,3,5},{2,4,6}
返回值：{1,2,3,4,5,6}

示例2

输入： {},{}
返回值：{}

示例3

输入： {-1,2,4},{1,3,4}
返回值：{-1,1,2,3,4,4}

代码

代码1 正常方法，遍历改变指向

1. 从两个链表最小的头结点开始遍历
2. 比较当前链表上L1的下一个节点current.next与另外一条链表L2等待比较的节点nextWaitNode的大小
   1. 如果当前链表的下一个节点比nextWaitNode大，就改变指向
   2. 如果不大，就继续在当前链表上遍历

（自己写的代码）

function Merge(pHead1, pHead2){
    // 1. 若果两个链表有一个为空，返回另一个，如果都为空，返回空
    if(pHead1===null || pHead2 ===null) {
        return pHead1 || pHead2
    }
    
    let nextWaitNode = null // 下一个等待比较的节点
    let newHead = null // 当前最小的节点
    
    // 找到小的那个开始遍历
    if(pHead1.val <= pHead2.val){
        newHead = pHead1
        nextWaitNode = pHead2
    }else {
        newHead = pHead2
        nextWaitNode = pHead1
    }
    
    let current = newHead
    
    while(current){
        // 如果current有next
        if(current.next){
            // 如果比另外一个链上等待比较的节点大，就切换
            if(current.next.val > nextWaitNode.val){
                let tempNode = current.next
                current.next = nextWaitNode // 切换
                nextWaitNode = tempNode
            }
            current = current.next
        }else { // 如果current没有next
            current.next = nextWaitNode 
            // 剩下的就不用比较了，因为是有序的，直接break
            break
        }
    }
    
    return newHead
}

（参考代码）

function Merge(pHead1, pHead2){
    // 虚拟节点
    let vHead = new ListNode(-1)
    // 当前指针
    let current = vHead
    
    while(pHead1 && pHead2){
        // 一个一个比较
        // 把current指向小的节点
        if(pHead1.val <= pHead2.val){
            current.next = pHead1 // 每条链表比较完一个就后移一位
            pHead1 = pHead1.next
        }else {
            current.next = pHead2 // 每条链表比较完一个就后移一位
            pHead2 = pHead2.next
        }
        
        current = current.next // current也后移一位，等待下次循环
    }
    // while循环会在某一条链表为空时结束
    // 将当前的current指向不为空的那一条
    current.next = pHead1 ? pHead1 : pHead2
    
    return vHead.next
}

代码2 递归

/*
1. 递归函数结束的条件是什么？
2. 递归函数一定是缩小递归区间的，那么下一步的递归区间是什么？
    对于问题1.对于链表就是，如果为空，返回什么
    对于问题2，跟迭代方法中的一样，如果PHead1的所指节点值小于等于pHead2所指的结点值，
    那么phead1后续节点和pHead节点继续递归
*/
function Merge(pHead1, pHead2){
    if(!pHead1) return pHead2
    if(!pHead2) return pHead1
    
    if(pHead1.val <= pHead2.val){
        pHead1.next = Merge(pHead1.next, pHead2)
        return pHead1
    }else {
        pHead2.next = Merge(pHead1, pHead2.next)
        return pHead2
    }
}

题目来源

JZ25 合并两个排序的链表