链表-0405合并有序链表

import java.util.*;
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode res = new ListNode(-1);
        ListNode cur = res;   
        while(list1!=null && list2!=null){
            if(list1.val<=list2.val){
                cur.next=list1;
                list1=list1.next;
                cur=cur.next;       
            } 
            else{
                cur.next=list2;
                list2=list2.next;
                cur=cur.next;
            }           
        }
        if(list1==null) cur.next=list2;
        else cur.next=list1;
        return res.next;
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

合并k个有序链表

一. 数组

法一，最简单的，把所有的节点遍历一遍，存到数组中，在数组中排序后再重新建链表。
遍历O(N)+排序O(NlogN),空间复杂度O（N）

import java.util.*;
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
       // ArrayList array = new ArrayList();写错的地方
        ArrayList<Integer> array = new ArrayList<Integer>();
        ListNode head = null;
        for(int i=0;i<lists.size(); i++){
            head = lists.get(i);
            while(head!=null){
                array.add(head.val);
                head = head.next;
            }
        }
        Collections.sort(array);
        head = new ListNode(-1);
        ListNode res = head;
        for(int i =0; i<array.size(); i++){
            ListNode cur = new ListNode(array.get(i));           
            head.next = cur;
            head = cur;        
        }
        return res.next;
       
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

这种做法太简单，肯定不是出题者想看到的做法，但是我在写这个的时候还是出了问题，对java太不熟
正确的写法是：

ArrayList array = new ArrayList()
1

但是我漏了前面第一个Integer，后面报错找了很久！！！太弱智了！！！！

2. 归并

import java.util.*;
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        return merge(lists, 0, lists.size()-1);     
    }
    public ListNode merge(ArrayList<ListNode> lists, int a, int b){
        if(a>b) return null;
        else if(a==b) return lists.get(a);
        else{
            int mid = (a+b)/2;
            return mergeTwoLists(merge(lists,a,mid), merge(lists,mid+1,b));
        }
        
    }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2){
        ListNode res = new ListNode(-1);
        ListNode head = res;
        while(list1!=null && list2!=null){
            if(list1.val<list2.val){
                res.next = list1;
                list1 = list1.next;
                res = res.next;                     
            }
            else{
                res.next = list2;
                list2 = list2.next;
                res = res.next;            
            }
        }
        if(list1==null) res.next = list2;
        else res.next = list1;
        return head.next;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

时间复杂度分析：K 条链表的总结点数是 N，平均每条链表有 N/K 个节点，因此合并两条链表的时间复杂度是 O(N/K)。从 K 条链表开始两两合并成 11 条链表，因此每条链表都会被合并 logK 次，因此 KK 条链表会被合并 K * logK次，因此总共的时间复杂度是 KlogKN/K 即 O（NlogK）。