# Divide n Conquer, my java solution, what's the complexity?

• Basic idea is from divide and conquer, utilizing the function MergeTwoLists() from Question 23.

``````public class Solution {
private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1==null) return l2;
else if(l2==null) return l1;

ListNode dummy = new ListNode(0);
while(l1!=null||l2!=null){
if((l1==null?Integer.MAX_VALUE:l1.val)<=(l2==null?Integer.MAX_VALUE:l2.val)){
dummy.next=l1;
l1 = l1==null? l1:l1.next;
}else{
dummy.next=l2;
l2 = l2==null? l2:l2.next;
}
dummy=dummy.next;

}
}

while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}

}

ListNode right = sortList(mid.next);
mid.next = null;

return mergeTwoLists(left, right);
}

}``````

• The way you make the recursive calls is not an O(1) solution. To achieve O(1), you need to do merge sort from small step to large step ( 2,4,8,..).

• merge sort is O(n^2) in this problem because of the mid searching

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