# Merge two sorted lists

There are many if-else conditions in my code

### Question 1:

I am looking for suggestions to minimize if else conditions. Also, Code in Step 1 and Step2 is almost same. Is there any way to make it neat and improve readability

### Question 2:

I am looking for suggestions to improve main method and which methods can be called with an instance or class variables. That technique I will apply to all my LinkedList related questions

public class MergeTwoSortedLists {

static class Node {
int data;
Node next;

Node(int d) {
data = d;
next = null;
}
}

public void push(int data) {
Node n = new Node(data);
if ( head == null ) {
} else {
while (temp.next != null ) {
temp = temp.next;
}
temp.next = n;
}
}

public static void printList(Node head) {
while ( temp != null ) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}

public static void main(String[] args) {
MergeTwoSortedLists l1 = new MergeTwoSortedLists();
l1.push(1);
l1.push(2);
l1.push(13);
l1.push(14);
l1.push(50);

MergeTwoSortedLists l2 = new MergeTwoSortedLists();
l2.push(10);
l2.push(20);
l2.push(55);

printList(res);

}

Node s = null;
Node res = null;

/* Step 1: Set the s with less value */
} else {
}
}
res = s;

/* Step2: Iterate oer two lists and keep moving s accordingly */
} else {
}
}
if ( headA == null ) {
}
if ( headB == null ) {
}

return res;

}
}


Your push method takes time proportional to the length of the list. Usually I would expect this method to take constant time. How can you change your data structure to achieve this?

Your push method could also check (in constant time) that the sorted order is preserved, and throw an exception if the client tries to push an illegal int.

Probably your class ought to be called SortedList, since this is the object you’re implementing. Then your sortTwoLists() (which could be called mergeTwoLists()) would be an instance method taking a SortedList object as a parameter. Note that both SortedLists involved are changed by this method.

printList() would probably be better as an instance method (in which case, it needn’t take any parameters).

Question 1: Here’s one possible approach. You could build an auxiliary MergingNode class, with instance variables:

Node mergedNode; // a node in the merged list
Node thisNode; // current node in the first list you’re merging
Node thatNode; // current node in the second list you’re merging


This class could have methods getMergedNode(), which just returns mergedNode, and nextMergeStep(), which replaces mergedNode by the next node in the merged list and updates either thisNode or thatNode, depending on which list we took a node from. Note that nextMergeStep() modifies the original SortedLists.

Then, Step 1 can be replaced by

SortedList merged = new SortedList();
mergingNode.nextMergeStep();


Step 2 can be replaced by

Node curNode = merged.head;
while (curNode != null) {
mergingNode.nextMergeStep();
Node nextNode = mergingNode.getMergedNode();
curNode.next = nextNode;
curNode = nextNode;
}


This way the nextMergeStep() method does all the work of your if statements.

Question 2: To clean up your main method, you could, for example, write a constructor for SortedList that takes an array of integers as a parameter, and constructs the SortedList containing those integers (meanwhile checking that the array was sorted).