merging k sorted lists does not work with negative values C#

user_15292554 0
Viewed 66

The question for the problem is: You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it. A successful working example with inputs and outputs is:

Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
  1->4->5,
  1->3->4,
  2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6

The issue with my code is that it is not working for negative values however it works fine for positive values. eg input -> [[2],[1],[-1]] output->[1,2]

  public class Solution {
   public ListNode MergeKLists(ListNode[] lists) {
       if (lists.Length == 0) return null;
       var newlist = new ListNode();
       var result = newlist;
       for(int i=0; i<lists.Length; i++)
       {
           if(lists[i] !=null)
           newlist = MergeTwoLists(lists[i], newlist);
       }
       return result.next;
    }

    

    private 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;
        }
    }
}
merge list c#
1 Answers

Fundamentally, the problem with your code is that you initialize the algorithm with a non-empty list. I.e. you set newlist to a single ListNode object. You haven't provided a complete code example, but presumably this is a class with at least two members, val and next. In C#, both of these members will initially have their default values, which means you start out with the list [0], before you've even started merging anything.

Note also that while you are modifying the newlist variable in the merging loop, what you return is the result.next variable. This appears to be an attempt to skip the erroneously include 0 value that you put in the newlist list in the first place. But in your negative-valued example, it causes you to skip both the 0 value, and the -1 value that the merge correctly placed before it.

In your example [[2],[1],[-1]], this means that when the loop for merging is done, you have newlist referring to the list [-1, 0, 1, 2]. But result points to the second element of that list (the original 0-valued node), giving you [0, 1, 2]. Then what you return is the next node of that, which produces [1,2].

The fact is, the MergeTwoLists() method you show already handles empty, i.e. null-valued, lists. It's not clear what motivated you to initialize your algorithm with a non-empty list, nor what motivated you to keep a second variable to reference that same node. Your problem probably would've been easier for you to notice if you hadn't done the latter, and of course, the whole bug is caused by the former.

You should just remove both aspects from the code you already have. Initialize newlist to null instead of creating a new node for it, and get rid of the result variable altogether:

public ListNode MergeKLists(ListNode[] lists) {
    var newlist = null;
    for (int i = 0; i < lists.Length; i++)
    {
        if (lists[i] != null) {
            newlist = MergeTwoLists(lists[i], newlist);
        }
    }
    return newlist;
}

Note: you also don't need the check for lists.Length == 0. The loop will be skipped if lists.Length is 0, and with the fixed version just returning null as the empty list in that case, it works just as well without it.

On a more general note: most of the time, bugs are fixed by changing code, or even removing it. If you get into the habit of fixing bugs by adding code, more often than not you just wind up with a new bug added to the one you already had.

I will admit, that rule is not a hard-and-fast, 100% reliable one. But it's served me very well over the years.

user_35380120
Related