【LeetCode刷题-链表】--23.合并K个升序链表

23.合并K个升序链表

方法：顺序合并

在前面已经知道合并两个升序链表的前提下，用一个变量ans来维护以及合并的链表，第i次循环把第i个链表和ans合并，答案保存到ans中

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode ans = null;
        for(int i = 0;i<lists.length;i++){
            ans = mergeTwoLists(ans,lists[i]);
        }
        return ans;
    }
    
    //合并两个有序链表
    public ListNode mergeTwoLists(ListNode a,ListNode b){
        if(a == null || b == null){
            return a != null ? a : b;
        }
        ListNode head = new ListNode(0);  //定义一个头节点
        ListNode tail = head, aPtr = a, bPtr = b;
        while(aPtr != null && bPtr != null){
            if(aPtr.val < bPtr.val){
                tail.next = aPtr;
                aPtr = aPtr.next;
            }else{
                tail.next = bPtr;
                bPtr = bPtr.next;
            }
            tail = tail.next;
        }
        tail.next = (aPtr != null ? aPtr : bPtr);
        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