o2o 网站杭州最新消息

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;}
}