Straightforward idea for java in 3 steps


  • 0
    D
     Hope my comment is enough for reading the codes.
    
    public class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            if (lists.length == 0) return null;
            ListNode ret = new ListNode(0);
            ListNode cur = ret;
    
            //create ret list using while loop
            //Every time, I check available first, then get the min, add to the ret;
            while (checkExist(lists)) {
                int min = getMin(lists);
                ListNode newNode = new ListNode(min);
                cur.next = newNode;
                cur = cur.next;
            }
            return ret.next;
        }
        
        //check if lists have available ListNode[]
        public boolean checkExist(ListNode[] lists) {
            for (int i = 0; i < lists.length; i ++) {
                if (lists[i] != null) return true;  
            }
            return false;
        }
        
        //get the min value from lists
        public int getMin(ListNode[] lists) {
            int min = Integer.MAX_VALUE;
            int num = 0;
            for (int i = 0; i < lists.length; i ++) {
                if (lists[i] != null && lists[i].val < min) {
                    min = lists[i].val;
                    num = i;
                }
            }
            ListNode cur = lists[num];
            lists[num] = cur.next;
            return min;
        }
    }

  • 0
    M

    It is kind of confusing to me that the array has already sorted, so why you still need to iterate through all the ListNode in the List to find the min node?(if it s already sorted, the min should be the first node in a list, right?)


  • 0
    D

    Yes, but the reason I iterate is to find the smallest in each first node vale. Because only ListNode is sorted, but lists have several ListNode. I need to find the smallest from them.


  • 0
    M

    I don't really understand the code, hope you can help me to explain a little bit more. 1. Is the 'lists' array in your code represents the link lists? ( For example, like there are two linked list 1,3,5 and 2,4,6. ). 2. what is the function of 'lists[num] = cur.next;' in your code? Can I change it to lists[num] = null? 3. Are you Chinese? ...lol


  • 0
    D

    Yeah, I am Chinese, lol.

    1. Yes, it is link lists.
    2. 'lists[num] = cur.next;' means after you find the smallest, you should delete it and let the next one to be the first. This is how checkExist works, it confirms there is linked list != null, because we delete the smallest linkedList when we find it.

  • 0
    M

    It looks to me like you are sorting a bunch of numbers in a array then return them as a link list. It doesn't sounds like merge several different link lists together.


  • 0
    M
    This post is deleted!

Log in to reply
 

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