[LeetCode] Merge k Sorted Lists (Java)

Problem

Solution 1.

-T he number range of constraints is not large, so simply converting ListNode to List, sorting it, and returning it again. - - It exhibits poor time and space complexity results.

/**
 * 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) {
        List<Integer> mergeList = new ArrayList<>();
        for (ListNode l : lists) {
            ListNode curr = l;
            while (curr != null) {
                mergeList.add(curr.val);
                curr = curr.next;
            }
        }
        Collections.sort(mergeList);
        
        ListNode ans = new ListNode();
        ListNode tmp = ans;
        for (int i : mergeList) {
            tmp.next = new ListNode(i);
            tmp = tmp.next;
        }

        return ans.next;
    }
}

Solution 2.

- Using Merge Sort(divde-and-conquer)

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        
        // if there is only one ListNode, return immediately.
        if (lists == null || lists.length == 0) return null;
		
        return mergeLists(lists, 0, lists.length - 1);
    }

    private ListNode mergeLists(ListNode[] lists, int start, int end) { 
        
        if (start == end) return lists[start];
        
        if (start + 1 == end) return merge(lists[start], lists[end]);
		
        // using merge sort alogorithm
        // divide lists until it is split into halves
        int mid = start + (end - start) / 2;
        ListNode left = mergeLists(lists, start, mid);
        ListNode right = mergeLists(lists, mid + 1, end);
        
        return merge (left, right);
    }

    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode tmp = new ListNode(0);
        ListNode curr = tmp;
        
        // compare and sort the nodes of the list
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }
            curr = curr.next;
        }
		
        // if any list becomes null, 
        curr.next = (l1 != null) ? l1 : l2;

        return tmp.next;
    }
}