5
\$\begingroup\$

enter image description here

Here is my solution: I want to know if my solution fits the requirement 100%? Or if there is any better solution?

Constraint of the question:

  1. must be singly linkedlist
  2. must use recursion, and no helper methods allowed.
  3. The method must return the head node of the merged list.
class Solution{
    Node dummy=new Node(0,null);// the dummy node to store the merged result

    public   Node mergeAscend(Node a,Node b){
        if(a==null&&b==null){//base case
            return null;
        }
               
        else{
            if((a!=null&&b==null)||a.value>=b.value){// insert "b" after dummy
                //store the next node of current a, before pointing a.next to dummy.next;
                Node store_a_next_node=a.next;
                //insert Node "a" between dummy and dummy.next
                a.next=dummy.next;
                dummy.next=a;
                mergeAscend(store_a_next_node,b);
            }
            else if((a==null&&b!=null)||a.value<b.value){//insert "a" after dummy
                Node store_b_next_node=b.next;
                b.next=dummy.next;
                dummy.next=b;
                mergeAscend(a,store_b_next_node);
            }
        }
        return  dummy.next;
    }
}
class Node {
    public int value;
    public Node next;

    public Node(int value, Node next) {
        this.value = value;
        this.next = next;
    }
}
\$\endgroup\$
2
  • \$\begingroup\$ Hello, for information, the Node class is missing, it's a bit hard to do a proper code review when the code is not compiling. \$\endgroup\$
    – Doi9t
    Jun 19, 2020 at 23:24
  • \$\begingroup\$ Thank you for reminding me. I just added Node class \$\endgroup\$
    – Ziyu Zhong
    Jun 20, 2020 at 14:42

1 Answer 1

3
\$\begingroup\$

Compilation Error

The first problem is to solve the compiling error.

Just follow the interface:

    public Node<Integer> mergeAscend(Node<Integer> a, Node<Integer> b) 

Warnings and Code convention

You should add the type information to the store_next_a_node variable (and store_next_b_node). Additionally, in Java naming conversion, variable names use camel case. Therefore, I suggest substitute:

            Node store_next_a_node = a.next;
           ...
            Node store_next_b_node = b.next;

By...

            Node<Integer> nextNode = a.next;

Simple "Test Case"

The code bellow is just an example and not a full automated test (for more information, look for Java automated tests. eg: junit tutorial).But it is enough to give us some hints what is going on. For example, we can see the original code does not solve the problem. Let us write a simple test case:

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] a = { 6, 4, 2 };
        Node<Integer> h1 = new Node<>(8, null);
        Node<Integer> previous = h1;
        for (int value : a) {
            Node<Integer> node = new Node<>(value, null);
            previous.next = node;
            previous = node;
        }


        int[] b = { 7, 5, 3, 1 };
        Node<Integer> h2 = new Node<>(9, null);
        previous = h2;
        for (int value : b) {
            Node<Integer> node = new Node<>(value, null);
            previous.next = node;
            previous = node;
        }
        solution.mergeAscend(h1, h2);
        Node<Integer> iterator = solution.dummy;
        while (iterator != null) {
            System.out.println(iterator.value);
            iterator = iterator.next;
        }
    }

The expected output would be the numbers printed in ascending order as the exercise suggests.

NullPointerException

With the test case, we can execute the code and and we will get a null pointer exception during the execution:

Exception in thread "main" java.lang.NullPointerException
    at Solution.mergeAscend(Solution.java:13)
    at Solution.mergeAscend(Solution.java:19)
    at Solution.mergeAscend(Solution.java:24)
    at Solution.mergeAscend(Solution.java:19)
    at Solution.mergeAscend(Solution.java:24)
    at Solution.mergeAscend(Solution.java:19)
    at Solution.mergeAscend(Solution.java:24)
    at Solution.mergeAscend(Solution.java:19)
    at Solution.mergeAscend(Solution.java:24)
    at Solution.main(Solution.java:50)

Bug

If you look the code, the following statement is suspicious:

if((a!=null&&b==null)||a.value>=b.value)

What if a is null and b is not null? First condition is false and Java interpreter will try to evaluate the second condition. Unfortunately, a.value will throw a NullPointerException.

Next Step: How to fix it ?

Clean Code makes our life easier

Let's make the code cleaner . In our case, we want to preserve the original code ideas and just simplifying what is possible. Hopefully we will remove the conditions that make the code to fail.

Remove unnecessary else-statement

First, after the base case, we don't need a else-statement. Change..

        if (a == null && b == null) {//base case
            return null;
        }
        else {
        ...
        }

to

        if (a == null && b == null) {//base case
            return null;
        }
        ...

Nullability test only once

Second, remove the complication of testing a nullability all the time.

Just add the following check after the base case.

        if (a == null)
            return mergeAscend(b, a);

With that, now we know that a is the longest list and we don't need to check again and again that condition.

So, your second "if-statement" can be change from

        if ( (a!=null && b==null) || a.value >= b.value)

to:

        if (b == null || a.value >= b.value) // insert "b" after dummy

Remove unnecessary if-statement

After that, we might think about it... we don't need the third "if-statement". Just remove it.

 else if((a==null&&b!=null)||a.value<b.value){
     ...
 }

To...

 else {
      ...
  }

Congrats, your code now works!

    public Node<Integer> mergeAscend(Node<Integer> a, Node<Integer> b) {
        if (a == null && b == null) {//base case
            return null;
        }
        if (a == null)
            return mergeAscend(b, a);
        if (b == null || a.value >= b.value) {// insert "a" after dummy
            //store the next node of current a, before pointing a.next to dummy.next;
            Node<Integer> nextNode = a.next;
            //insert Node "a" between dummy and dummy.next
            a.next = dummy.next;
            dummy.next = a;
            mergeAscend(nextNode, b);
        } else {
            Node<Integer> nextNode = b.next;
            b.next = dummy.next;
            dummy.next = b;
            mergeAscend(a, nextNode);
        }
        return dummy.next;
    }

Test it!

PS: Another Minor Thing - Comment misleading

Your code comments are misleading. In the second if-statement, if the statement evaluate the expression as true, code below add a between dummy and dummy.next.

change

// insert "b" after dummy

To

// insert "a" after dummy

PS2: Symmetric symplification

Evaluating the code again, we might found the code is a little redundant. It means, part of the code is doing exactly the same thing, but the variable names are just swapped. In that case, we can simplify it further.

    public Node<Integer> mergeAscend(Node<Integer> a, Node<Integer> b) {
        if (a == null && b == null) {//base case
            return dummy.next;
        }
        if (a == null || (b != null && a.value < b.value)) { // symmetric case
            return mergeAscend(b, a);
        }
        //store the next node of current a, before pointing a.next to dummy.next;
        //insert Node "a" between dummy and dummy.next
        Node<Integer> nextNode = a.next;
        a.next = dummy.next;
        dummy.next = a;
        return mergeAscend(nextNode, b);
    }
\$\endgroup\$
1
  • \$\begingroup\$ Wow,Thank you soooo much for this super detailed explanation! I have learned a lot. \$\endgroup\$
    – Ziyu Zhong
    Jun 20, 2020 at 20:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.