合并排序链表

2018-08-20

合并两个有序的链表

两个有序链表的合并，一开始想到了插入排序的思想，但是算法时间复杂度太大了o(n2)，代码如下：

/**
 * 合并两个有序的链表，插入排序思想，时间复杂度o(n2)
 */
public class MergeList {
    public static ListNode Merge(ListNode list1,ListNode list2) {
        if (list2 == null) {
            return list1;
        }
        if (list1 == null) {
            return list2;
        }
        ListNode res = null;
        if (list1.val <= list2.val) {
            res = list1;
            while (list2 != null) {
                ListNode temp1 = list1;
                while (list1 != null && list1.val < list2.val) {
                    temp1 = list1;
                    list1 = list1.next;
                    if (list1 == null) {
                        break;
                    }
                }
                ListNode temp2 = list2.next;
                temp1.next = list2;
                list2.next = list1;
                list2 = temp2;
            }
            return res;
        } else {
            res = list2;
            while (list1 != null) {
                ListNode temp2 = null;
                while (list2 != null && list2.val < list1.val) {
                    temp2 = list2;
                    list2 = list2.next;
                    if (list2 == null) {
                        break;
                    }
                }
                ListNode temp1 = list1.next;
                temp2.next = list1;
                list1.next = list2;
                list1 = temp1;
            }
            return res;
        }

    }

    public static void main(String[] args) {
        ListNode l1 = new ListNode(2);
        ListNode l2 = new ListNode(4);
        ListNode l3 = new ListNode(6);
        ListNode l4 = new ListNode(1);
        ListNode l5 = new ListNode(3);
        ListNode l6 = new ListNode(5);

        l1.next = l2;
        l2.next = l3;

        l4.next = l5;
        l5.next = l6;
        ListNode res = Merge(l1, l4);
        while (res != null) {
            System.out.println(res.val);
            res = res.next;
        }


    }

}

本地测试用例通过，但是牛客网在线提交失败，后来有看到了一个递归的解法，觉得很是巧妙，自己写了一遍，代码如下：

public class Solution {
    public static ListNode Merge(ListNode list1,ListNode list2) {
        if (list2 == null) {
            return list1;
        }
        if (list1 == null) {
            return list2;
        }
        if (list1.val <= list2.val) {
            list1.next = Merge(list1.next, list2);
            return list1;
        } else {
            list2.next = Merge(list1, list2.next);
            return list2;
        }
    }
}