Clean code for both QuickSort and MergeSort


  • 0
    A

    public class Solution {
    public ListNode sortList(ListNode head) {

        //return mergeSort(head);
        return quickSort(head);
    }
    private ListNode quickSort(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        
        //Partition
        int p = head.val;//choose head as pivot
        ListNode dummy1 = new ListNode(0);//left part
        ListNode dummy2 = new ListNode(0);//right part
        ListNode midDummy = new ListNode(0);//mid part
        ListNode tail1 = dummy1;
        ListNode tail2 = dummy2;
        ListNode midTail = midDummy;
        ListNode cur = head;
        while(cur != null) {
            if(cur.val < p) {
                tail1.next = cur;
                tail1 = tail1.next;
            } else if(cur.val > p){
                tail2.next = cur;
                tail2 = tail2.next;
            } else {
                midTail.next = cur;
                midTail = midTail.next;
            }
            cur = cur.next;
        }
        tail1.next = null;
        tail2.next = null;
        midTail.next = null;
        
        //recursion
        ListNode left = quickSort(dummy1.next);
        ListNode right = quickSort(dummy2.next);
        
        //concat left, mid, and right part to get the final result.
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while(left != null) {
            tail.next = left;
            tail = tail.next;
            left = left.next;
        }
        tail.next = midDummy.next;
        
        midTail.next = right;
        return dummy.next;
        
    }
    
    private ListNode mergeSort(ListNode head) {
        
        if(head == null || head.next == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode head2 = slow.next;
        slow.next = null;
        return merge(mergeSort(head), mergeSort(head2));
    }
    
    private ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        while(head1 != null && head2 != null) {
            if(head1.val < head2.val) {
                tail.next = head1;
                head1 = head1.next;
            } else {
                tail.next = head2;
                head2 = head2.next;
            }
            tail = tail.next;
        }
        if(head1 != null) {
            tail.next = head1;
        }
        if(head2 != null) {
            tail.next = head2;
        }
        return dummy.next;
    }
    

    }


Log in to reply
 

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