# Java Solution without recursion (Feel free to comment)

• ``````public class Solution {

public ListNode mergeKLists(List<ListNode> lists) {

//Base case where list size is 0 or 1
if(lists.size() == 0){
return null;
}
if(lists.size() == 1){
ListNode l = lists.get(0);
return lists.get(0);
}

while(lists.size() > 1){
int size = lists.size();
ArrayList<Integer> remove_index = new ArrayList<Integer>();

//Compare a pair of lists at a time and merge into a single list and remove the 2nd list of the pair
for(int i = 0; i < size-1; i= i+2){
ListNode l1 = lists.get(i);
ListNode l2 = lists.get(i+1);
lists.set(i, merge(l1,l2));
}

//Remove lists that have already been compared, starting from the larger index so it wont have index issues
for(int i=remove_index.size()-1; i >= 0; i--){
int r = remove_index.get(i);
lists.remove(r);
}
}

//Finally only 1 sorted list is left and returns that list
return lists.get(0);
}

//Merge the 2 input lists

public ListNode merge(ListNode l1, ListNode l2){

if(l1 == null){
return l2;
}
if(l2 == null){
return l1;
}
ListNode result = new ListNode(0);

//Pick the smaller value and append to the result list
while(l1 != null && l2 != null){
if(l1.val <= l2.val){
result.next = l1;
result = result.next;
l1 = l1.next;
}
else{
result.next = l2;
result = result.next;
l2 = l2.next;
}

}
if(l1 != null){
result.next = l1;
}
if(l2 != null){
result.next = l2;
}