Qi

Cogito ergo sum

0%

leetcode 23 Solution

发表于 更新于 分类于 226 1 分钟

代码解析

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
package com.demo.s23;

/**
 * 合并K个升序链表
 * 给你一个链表数组，每个链表都已经按升序排列。
 *
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 */

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class Solution {
    public ListNode merge2Lists(ListNode lista, ListNode listb) {
        //哑巴节点方便返回链表head
        ListNode dum = new ListNode();
        //遍历链表 cur 为当前节点
        ListNode cur = dum;
        while(true) {
            //遍历完lista
            if(lista == null) {
                cur.next = listb;
                break;
            }
            //遍历完listb
            if(listb == null) {
                cur.next = lista;
                break;
            }
            //按照升序排列链表
            if(lista.val <= listb.val) {
                cur.next = lista;
                lista = lista.next;
            } else {
                cur.next = listb;
                listb = listb.next;
            }
            //链表节点后移一位
            cur = cur.next;
        }
        return dum.next;
    }

    //多个链表合并，变为两两合并
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length == 0) {
            return null;
        }
        if(lists.length == 1) {
            return lists[0];
        }
        ListNode dum = null;
        //多个链表两两合并
        for(int i =0 ;i < lists.length; i ++) {
            dum = merge2Lists(dum, lists[i]);
        }
        return dum;
    }
}