A java solution based on mergesort


  • 0
    W

    """
    /**

    • Definition for singly-linked list.
    • public class ListNode {
    • int val;
      
    • ListNode next;
      
    • ListNode(int x) { val = x; }
      
    • }
      */
      public class Solution {
      public ListNode mergeKLists(ListNode[] lists) {
      if(lists.length == 0){
      return null;
      }
      if (lists.length == 1){
      return lists[0];
      }else if (lists.length == 2){
      return mergetwoList(lists[0],lists[1]);
      }else {
      return mergetwoList(mergeKLists(Arrays.copyOfRange(lists,0,lists.length/2)),
      mergeKLists(Arrays.copyOfRange(lists,lists.length/2,lists.length)));
      }
    }
    private ListNode mergetwoList(ListNode p1,ListNode p2){
        ListNode head = new ListNode(0);
        ListNode p = head;
        while (p1!=null&&p2!=null){
            if (p1.val<p2.val){
                p.next = p1;
                p1 = p1.next;
            }else {
                p.next = p2;
                p2 = p2.next;
            }
            p = p.next;
        }
        if (p1!=null){
            p.next = p1;
        }
        if (p2!=null){
            p.next = p2;
        }
        return head.next;
    }
    

    }
    """


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.