Share merge sort in array and linkedlist to compare


  • 0
    C
    // 148 : sort list 
    // merge sort in array : 7ms
    public ListNode sortList(ListNode head) {
    	if(head == null || head.next == null) return head;
    	// find the middle of linkedlist
    	ListNode fast = head, slow = head, pre = null;
    	while(fast != null && fast.next != null){
    		pre = slow;
    		slow = slow.next;
    		fast = fast.next.next;
    	}
    	pre.next = null;
    	// Conquer(sort) and merge
    	ListNode l1 = sortList(head);
    	ListNode l2 = sortList(slow);
    	return merge(l1, l2);
    }
    private ListNode merge(ListNode l1, ListNode l2){
    	ListNode dummy = new ListNode(0), rear = dummy;
    	while(l1 != null && l2 != null){
    		if(l1.val < l2.val){
    			rear.next = l1;
    			l1 = l1.next;
    		}
    		else{
    			rear.next = l2;
    			l2 = l2.next;
    		}
    		rear = rear.next;
    	}
    	if(l1 != null) rear.next = l1;
    	if(l2 != null) rear.next = l2;
    	return dummy.next;
    }
    
    // merge sort in array : 7ms
    public ListNode sortList1(ListNode head) {
        int[] nums = new int[getLinkedListLength(head)];
        int index = 0;
        for(ListNode p = head; p != null; p = p.next){
        	nums[index++] = p.val;
        }
        mergeSort(nums);
        index = 0;
        for(ListNode p = head; p != null; p = p.next){
        	p.val = nums[index++];
        }
        return head;
    }
    private int getLinkedListLength(ListNode head){
    	int length = 0;
    	while(head != null){
    		length++;
    		head = head.next;
    	}
    	return length;
    }
    private void mergeSort(int[] nums){
    	int[] tempArr = new int[nums.length];
    	mergeSort(nums, tempArr, 0, nums.length - 1);
    }
    private void mergeSort(int[] nums, int[] tempArr, int left, int right){
    	if(left < right){
    		int center = (left + right) / 2;
    		mergeSort(nums, tempArr, left, center);
    		mergeSort(nums, tempArr, center + 1, right);
    		merge(nums, tempArr, left, center + 1, right);
    	}
    }
    private void merge(int[] nums, int[] tempArr, int leftPos, int rightPos, int rightEnd){
    	int leftEnd = rightPos - 1;
    	int tempPos = leftPos;
    	int numElements = rightEnd - leftPos + 1;
    	while(leftPos <= leftEnd && rightPos <= rightEnd){
    		if(nums[leftPos] < nums[rightPos]) tempArr[tempPos++] = nums[leftPos++];
    		else tempArr[tempPos++] = nums[rightPos++];
    	}
    	while(leftPos <= leftEnd){
    		tempArr[tempPos++] = nums[leftPos++];
    	}
    	while(rightPos <= rightEnd){
    		tempArr[tempPos++] = nums[rightPos++];
    	}
    	for (int i = 0; i < numElements; i++, rightEnd--) {
    		nums[rightEnd] = tempArr[rightEnd];
    	}
    }

Log in to reply
 

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