# 2ms Easy to understand Java Solution with explanation and O(n) complexity

• Main rationale here is to have a backup List which we we will keep on appending as we find the next higher number

We put a boundary conditions first like if list 1 is empty then return list 2 and vice versa
If both are null then return null

Then we start while loop in which terminating condition is that both list should be iterated

We start from head of list and whichever list has small element that we put in backup list and increment pointer for that last because we are done with that element

If both have same element then add that element twice (my iniital test case failed because I was not handling this)
In the end we get merged sorted list

We return back.up.next because we initialized backup with some random value (0 on this case)
...
/**

• public class ListNode {

• ``````int val;
``````
• ``````ListNode next;
``````
• ``````ListNode(int x) { val = x; }
``````
• }
*/
public class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

`````` ListNode ans = new ListNode(0);
ListNode backup = ans;

if(l1==null && l2==null) {
return null;
}

if(l1==null && l2!=null) {
return l2;
}

if(l2==null && l1!=null) {
return l1;
}
while(l1!=null || l2!=null) {
//check which one is smaller
if(l1==null && l2!=null) {
ans.next = new ListNode(l2.val);
ans = ans.next;
l2 = l2.next;
continue;
}

if(l2==null && l1!=null) {
ans.next = new ListNode(l1.val);
ans = ans.next;
l1 = l1.next;
continue;
}

if(l1.val<l2.val) {
ans.next = new ListNode(l1.val);
ans = ans.next;
l1 = l1.next;
}
else if(l1.val==l2.val) {
ans.next = new ListNode(l1.val);
ans = ans.next;
ans.next = new ListNode(l2.val);
ans = ans.next;
l1 = l1.next;
l2 = l2.next;
}
else {
ans.next = new ListNode(l2.val);
ans = ans.next;
l2 = l2.next;
}
}
return backup.next;
``````

}
}
...

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