题解 | #合并k个已排序的链表#

using System;
using System.Collections.Generic;

/*
public class ListNode
{
    public int val;
    public ListNode next;

    public ListNode (int x)
    {
        val = x;
    }
}
*/

class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类一维数组
     * @return ListNode类
     */
    public ListNode Merge(ListNode phead1, ListNode phead2) {
        ListNode t = new ListNode(-1);
        ListNode tail = t;
        while (phead1 != null && phead2 != null) {
            if (phead1.val < phead2.val) {
                tail.next = phead1;
                phead1 = phead1.next;
            } else {
                tail.next = phead2;
                phead2 = phead2.next;
            }
            tail = tail.next;
        }
        tail.next = phead2 == null ? phead1 : phead2;
        return t.next;
    }
    public ListNode mergeKLists(List<ListNode> lists) {
        // write code here
        if (lists.Count == 0) return null;
        int count = lists.Count - 1; //需要合并的次数
        for (int i = 0; i < count; i++) {
            lists[i + 1] = Merge(lists[i], lists[i + 1]);
        }
        return lists[lists.Count - 1];
    }
}