leetcode solves the linked list merge problem in one step

1、合并两个有序链表

21.合并两个升序链表

题目描述：

 

 思路：Merging two ordered linked lists is also a very classic problem,看到这道题目,Many of my friends will probably feel a sense of déjà vu,是不是有点像,Merge two arrays hahahaha,So let's use the dumb method first(依次比较)l来试试

1、依次比较

看看代码：

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode cur = new ListNode(0);
        ListNode result = cur;
        ListNode temp1 = list1;
        ListNode temp2 = list2;
        while (temp1 != null && temp2 != null){
            if (temp1.val < temp2.val){
                cur.next = temp1;
                temp1 = temp1.next;
                cur = cur.next;
            }else {
                cur.next = temp2;
                temp2 = temp2.next;
                cur = cur.next;
            }
        }
        if (temp1 == null){
            while (temp2 != null){
                cur.next = temp2;
                temp2 = temp2.next;
                cur = cur.next;
            }
        }else if (temp2 == null){
            while (temp1 != null){
                cur.next = temp1;
                temp1 = temp1.next;
                cur = cur.next;
            }
        }
        return result.next;
    }

时间复杂度：O(n)

空间复杂度：O(1)

2、递归

思路：Since it is recursion, we will think of the three recursive elements of this question

• 终止条件：list1为空,或者list2为空
• 返回值：Each layer returns a sorted linked list
• Native recursive content：如果list1.val更小,则将list1.nextJoin with the next level sorted linked list;list2反之亦然

我们看看代码：

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

时间复杂度：O(m+n),m为list1的长度,n为list2的长度

2、合并k个升序链表

23.合并k个升序链表

题目描述：

思路：拿到题目,First, let's examine the question,合并k条,Essentially and merge2A linked list in ascending order makes no difference,we just need to split,把k条链表,拆分成若干个2条链表,Thinking moment is clear!

至于如何拆分,I don't know if you all know 归并排序 ,If you don't know, you can move归并排序

The idea used in merge sort is to divide and conquer,先分后治,先拆分,后合并,Something to do with this problem we have the same effect,split the list first,merge the linked list;The only difference is when merge sort,We are splitting the same array,And now we are splitkdifferent linked lists,But we want the same result！

了解完之后,Let's look at the code：

 public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length < 1) return null;
        return mergeLists(lists, 0, lists.length);
    }
  
    public ListNode mergeLists(ListNode[] lists, int left, int right) {
        if (left >= right) return lists[left];
        int mid = (left + right) / 2;
        //先分
        ListNode l1 = mergeLists(lists, left, mid);
        ListNode l2 = mergeLists(lists, mid + 1, right);
        //后治
        return mergeTwoLists(l1, l2);

    }

    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;

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

Here in order to optimize the time complexity of our merging algorithm,We can use an iterative algorithm,That is first question of the first one to replace the merger recursive method,will speed up a lot of time

public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length < 1) return null;
        return mergeLists(lists, 0, lists.length);
    }

    public ListNode mergeLists(ListNode[] lists, int left, int right) {
        if (left >= right) return lists[left];
        int mid = (left + right) / 2;
        //先分
        ListNode l1 = mergeLists(lists, left, mid);
        ListNode l2 = mergeLists(lists, mid + 1, right);
        //后治
        return mergeTwoLists(l1, l2);

    }
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode cur = new ListNode(0);
        ListNode result = cur;
        ListNode temp1 = list1;
        ListNode temp2 = list2;
        while (temp1 != null && temp2 != null){
            if (temp1.val < temp2.val){
                cur.next = temp1;
                temp1 = temp1.next;
                cur = cur.next;
            }else {
                cur.next = temp2;
                temp2 = temp2.next;
                cur = cur.next;
            }
        }
        if (temp1 == null){
            while (temp2 != null){
                cur.next = temp2;
                temp2 = temp2.next;
                cur = cur.next;
            }
        }else if (temp2 == null){
            while (temp1 != null){
                cur.next = temp1;
                temp1 = temp1.next;
                cur = cur.next;
            }
        }
        return result.next;
    }

总结：合并升序链表,It is also a frequently asked question in the written test.,Everyone needs to learn~