# O N(log N) Iterative merge in Java

• I'm noticing that some of these "hard" problems end up having stupid-simple solutions, and the trick is being able to see the solution. I don't know if that is going to be true for all of them, but so far, it has been the case for the ones I've tried.

``````public class Solution {
public ListNode mergeKLists(ListNode[] lists) {
ListNode result = null;

if ( lists.length > 0 ) {
if ( lists.length > 1 ) {
int half = lists.length;
while ( half > 1 ) {
if ( half % 2 != 0 ) {
lists[0] = merge(lists[0], lists[--half]);
}

half = half/2;
for ( int n=0; n<half; n++ ) {
lists[n] = merge(lists[n], lists[half+n]);
}
}
}

result = lists[0];
}

return result;
}

private ListNode merge(ListNode list1, ListNode list2) {
ListNode result = null;
ListNode last = null;

while ( list1 != null && list2 != null ) {
ListNode min;

if ( list1.val <= list2.val ) {
min = list1;
list1 = list1.next;
} else {
min = list2;
list2 = list2.next;
}

if ( last == null ) {
result = last = min;
} else {
last.next = min;
last = last.next;
}
}

if ( last != null ) {
last.next = (list1 != null ? list1 : list2);
} else {
result = (list1 != null ? list1 : list2);
}

return result;
}
}``````

• It is not O(logn)

• Well, thank you for noticing my typo. I suppose if you know what it isn't, you must know what it is.

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