题解 | #合并两个排序的链表#

合并两个排序的链表

http://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337

算法思想一：迭代

解题思路：

设置result为哑结点，放置于新链表之前，最后返回的就是result.next；设置cur为当前节点，从result开始
当两个链表都非空时进入循环，令新链表的下一个节点cur.next为val更小的节点，相应的链表节点后移一位，每次循环记得cur也要后移一位
如果循环结束后还有链表非空，cur指向非空链表，返回result.next

图解：

代码展示：

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
        
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        if not pHead1:
            return pHead2
        if not pHead2:
            return pHead1
        
        result = ListNode(-1)
        cur = result
        while pHead1 and pHead2:
            # 元素对比
            if pHead1.val <= pHead2.val:
                cur.next = pHead1
                pHead1 = pHead1.next
            else:
                cur.next = pHead2
                pHead2 = pHead2.next
            # 指针右移动一位
            cur = cur.next
        # 拼接未对比的链表
        cur.next = pHead1 if pHead1 else pHead2
        return result.next

复杂度分析：

时间复杂度O(N+M)：M N分别表示pHead1, pHead2的长度

空间复杂度O(1)：常数级空间

算法思想二：递归

解题思路：

特殊情况：如果有一个链表为空，返回另一个链表
如果pHead1 节点值比小pHead2，下一个节点应该是 pHead1，应该return pHead1，在return之前，指定pHead1的下一个节点应该是pHead1.next和pHead2俩链表的合并后的头结点
如果pHead1 节点值比pHead2大，下一个节点应该是pHead2，应该return pHead2，在return之前，指定pHead2的下一个节点应该是pHead1和pHead2.next俩链表的合并后的头结点

代码展示：

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        // list1 list2为空的情况
        if(list1 == null || list2 == null){
            return list1 != null ? list1 : list2;
        }
        // 两个链表元素依次对比
        if(list1.val <= list2.val){
            // 递归计算 list1.next, list2
            list1.next = Merge(list1.next, list2);
            return list1;
        }else{
            // 递归计算 list1, list2.next
            list2.next = Merge(list1, list2.next);
            return list2;
        } 
    }
}

复杂度分析：

时间复杂度O(N+M)：M N分别表示pHead1, pHead2的长度

空间复杂度O(N+M)：迭代次数占用空间

算法思路三：借助额外数组

解题思路：

(1) 创建额外存储数组 nums

(2) 依次循环遍历 pHead1, pHead2，将链表中的元素存储到 nums中，再对nums进行排序

(3) 依次对排序后的数组 nums取数并构建合并后的链表

图解：

代码展示：

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        // list1 list2为空的情况
        if(list1==null) return list2;
        if(list2==null) return list1;
        if(list1 == null && list2 == null){
            return null;
        }
        //将两个两个链表存放在list中
        ArrayList<Integer> list = new ArrayList<>();
        // 遍历存储list1
        while(list1!=null){
            list.add(list1.val);
            list1 = list1.next;
        }
        // 遍历存储list2
        while(list2!=null){
            list.add(list2.val);
            list2 = list2.next;
        }
        // 对 list 排序
        Collections.sort(list);
        // 将list转换为 链表
        ListNode newHead = new ListNode(list.get(0));
        ListNode cur = newHead;
        for(int i=1;i<list.size();i++){
            cur.next = new ListNode(list.get(i));
            cur = cur.next;
        }
        // 输出合并链表
        return newHead;
    }
}