LeetCode之23. Merge k Sorted Lists

时间:2022-02-23 19:46:35

23题是一个综合性的题目,用前面做过的简单题目的累加就可以解出这一道题了,这道题最简单的办法是分治法,两两排序,最后再合并到一起,但是由于输入的是一个数组,所以此处不能用递归,21题可以作为它的子函数。

(分治法)

C# 代码

/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int x) { val = x; } * } */
public class Solution {
    public ListNode MergeKLists(ListNode[] lists) 
    {

        int Len = lists.Length;
        if(Len ==0 ) return null;

        ListNode MergedList =lists[0];
        for(int i =1; i<Len; i++)
        {
            MergedList = MergeList(MergedList, lists[i]);
        }

        return MergedList;

    }

    public ListNode MergeList(ListNode headA,ListNode headB)
    {
        if(headA == null) return headB;
        if(headB == null) return headA;
        ListNode result = new ListNode(0);
        ListNode Hc = result;
        while(headA != null && headB != null)
        {
            if(headA.val > headB.val)
            {
                Hc.next = headB;
                headB = headB.next;
            }
            else
            {
                Hc.next = headA;
                headA = headA.next;
            }
            Hc = Hc.next;
        }
        if(headA != null){
            headB = headA;
        }
        while(headB != null)
        {
            Hc.next = headB;
            headB = headB.next;
            Hc = Hc.next;
        }
        return result.next;
    }
}