[LeetCode] Merge k Sorted Lists

Thought:
Basically, we could merge every list into the first, the complexity will be nl1 + (n-1)l2 + ... + 1*ln;
To be faster, we could merge the first and the last, recursively. The complexity will be lgn*(l1 + l2 + ... + ln).
Using randomization, we could cancel out the difference between l1 - ln.
So the first method will result in the time O(n^2), while the second one is O(nlgn).

Code 1:
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if (lists.size() == 0) return null;
        for (int i = 1; i < lists.size(); i++) {
            lists.set(0, mergeTwoLists(lists.get(0), lists.get(i)));
        }
        return lists.get(0);
    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }else {           
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }    
    }
}

Code 2:
public class Solution {
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        int len = lists.size();
        if (len == 0) return null;
        int start = 0;
        int end = len - 1;
        while (len > 1) {
            lists.set(start, mergeTwoLists(lists.get(start), lists.get(end)));
            start++;
            end--;
            if (start >= end) {
                len = (len + 1) / 2;
                start = 0;
                end = len - 1;
            }
        }
        return lists.get(start);
    }
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        }else {           
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }    
    }
}