[数据结构与算法]【LeetCode - Java】21. 合并两个有序链表 （简单）

1. 题目描述

2. 解题思路

这类题目属于经典的数据结构类的题目，了解链表特性之后就很好入手了。首先常规思路有两种，一是使某个列表中的元素插入到另外一个链表中形成符合要求的有序链表；另外一种思路是生成一个新的链表，把两个旧链表中符合要求的元素添加到新链表中。

插入式的处理相对生成式更麻烦一点，需要判断使用哪一个旧链表作为基准，按照该题目的要求应是选择开头元素小的链表作为插入基准，在此之前还需要进行非空判断，不然会出现空指针异常。

除此以外，这道题目还可以基于递归的思想进行。递归的功能就是求出当前结点的元素以及后继的子链表，这种思路其实也是类似于插入式的处理思想。

3. 代码实现

3.1 插入式

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode pre;
        ListNode list;
        if(list1==null)
            return list2;
        else if(list2==null)
            return list1;
        else if (list1.val < list2.val) {
            list = list1;
            list1 = list1.next;
        } else {
            list = list2;
            list2 = list2.next;
        }
        pre = list;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                pre.next = list1;
                list1 = list1.next;
            } else {
                pre.next = list2;
                list2 = list2.next;
            }
            pre = pre.next;
        }
        pre.next = list1 == null ? list2 : list1;
        return list;
    }

3.2 生成式

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode pre;
        ListNode list = new ListNode();
        pre = list;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                pre.next = list1;
                list1 = list1.next;
            } else {
                pre.next = list2;
                list2 = list2.next;
            }
            pre = pre.next;
        }
        pre.next = list1 == null ? list2 : list1;
        return list.next;
    }

3.3 递归式

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null)
            return list2;
        else if (list2 == null)
            return list1;
        else {
            if (list1.val < list2.val) {
                list1.next = mergeTwoLists(list1.next, list2);
                return list1;
            } else {
                list2.next = mergeTwoLists(list1, list2.next);
                return list2;
            }
        }
    }

这种实现方式为本题目性能相对最优的解法。

3.4 对比

上述的三种方法的时间复杂度都是O(m+n)，m和n分别为两个链表的长度，因此三种算法在时间性能上没有差异。而在空间复杂度上，生成式算法因为需要生成新的链表，因此空间占用上相对其他算法更大。递归式的解法虽然在本题目中是可行的，因为本题目的节点个数不超过50，但若节点个数太大则容易发生栈溢出的情况。