How to merge two descending singly linkedlist into one ascending linkedlist using Recursion without any helper method?

Question

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;
 }
}

• Doi9t: 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.
• Ziyu Zhong: Thank you for reminding me. I just added Node class

Answer 1

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);
 }

• Ziyu Zhong: Wow,Thank you soooo much for this super detailed explanation! I have learned a lot.