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

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类ArrayList 
     * @return ListNode类
     */
    public ListNode mergeKLists (ArrayList<ListNode> lists) {
        // write code here

        if(lists == null) {
            return null;
        }

        int size = lists.size();
        if(size == 0) {
            return null;
        }
        ListNode end = lists.get(size -1);
        for(int i = size -2; i>=0; i--) {
            if(lists.get(i) == null) {
                continue;
            }
            System.out.println("i: " + i + "start");
            end = Merge(lists.get(i) , end);
            System.out.println("i: " + i + "end");
        }
        System.out.println("end");
        return end;
    }


public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        // write code here
        
        if(pHead1 == null) {
            return pHead2;
        }        
        if(pHead2 == null) {
            return pHead1;
        }        
        
        ListNode loop1,loop2 = null;
        if(pHead2.val >= pHead1.val) {
            loop1 = pHead1;
            loop2 = pHead2;
        } else {
            loop1 = pHead2;
            loop2 = pHead1;
        }

        while (true) {
            System.out.println("outside loop1:" + loop1.val);
            while (loop2 != null) {
                // System.out.println("loop2:" + loop2.val);
                // System.out.println("loop1:" + loop1.val);
                // System.out.println("loop1 next:" + loop1.next);
                if(loop2.val >= loop1.val && (loop1.next == null || loop2.val <= loop1.next.val)) {
                    ListNode swapTemp1 = loop1.next;                    
                    ListNode loop2Head = loop2;
                    // System.out.println("loop2Head:" + loop2Head.val);
                    loop2 = loop2.next;
                    loop1.next = loop2Head;
                    loop2Head.next = swapTemp1;
                    loop1 = loop1.next;
                } else {
                    break;
                }
            }
            loop1 = loop1.next;
            if(loop1 == null) {
                break;
            }
        }
        if(pHead2.val >= pHead1.val) {
            return pHead1;
        } else {
            return pHead2;
        }        
    }

}