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


  • -2
    R

    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;
        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;
    
        }
        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
    S

    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
    N

    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.