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

  • -2

    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);
        ListNode head=dummy;
                l1 = l1==null? l1:l1.next;
                l2 = l2==null? l2:l2.next;
        return head.next;
    private ListNode findMiddle(ListNode head){
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        return slow;
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        ListNode mid = findMiddle(head);
        ListNode right = sortList(mid.next);
        mid.next = null;
        ListNode left = sortList(head);
        return mergeTwoLists(left, right);

  • 0

    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,..).

  • 0

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

Log in to reply

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