148. Sort List

Problem Statement

Pattern:

---

Solution

private ListNode getMid (ListNode head) {
	ListNode slow = head, fast = head;
	fast = fast.next;
	
	while (fast!= null && fast.next!=null) {
		slow = slow.next;
		fast = fast.next.next;
	}
	// when fast / fast.next becomes null, slow would have reached floor of mid
	return slow;
}
 
private ListNode merge(ListNode left, ListNode right) {
	ListNode dummy = new ListNode(-1), tail = dummy;
	
	// merge left and right
	while(left != null && right != null) {
		if(left.val <= right.val) {
			tail.next = left;
			left = left.next;
		} else {  // right.val < left.val
			tail.next = right;
			right = right.next;
		}
		tail = tail.next;
	}
	
	// merge left
	while (left != null) {
		tail.next = left;
		left = left.next;
		tail = tail.next;
	}
	
	// merge right
	while (right != null ) {
		tail.next = right;
		right = right.next;
		tail = tail.next;
	}
	
	return dummy.next;
}
 
public ListNode sortList (ListNode head){
	// return if single el
	if (head == null || head.next == null) return head;
	
	// set left, mid right
	ListNode left = head;
	ListNode mid = getMid(head);
	ListNode right = mid.next;
	
	// disconnect mid
	mid.next = null;
 
	// RECURSE for left and right sublist
	left = sortList(left);
	right = sortList(right);
	
	// WAY UP
	return merge(left, right);
}

Notes

Sort List - Merge Sort - Leetcode 148 - YouTube

• getMid from 876. Middle of the Linked List
• sortList as expected partitions the array, ,into left and right, and sets the mid partition to null
  • recruse for left and right on the way down
  • return merged list on the way up
• Interestingly for linkedlists you dont need to init a seperate linked list, to store the merged array, since you can point a your tail to the next left or right