Leetcode: Sort List

Sort a linked list in O(n log n) time using constant space complexity.
Understand the problem:
The problem is very straight-forward. The only requirement is O(n logn) time complexity, so it indicates to use quick sort or merge sort. 

In this question we choose the merge sort because quick sort requires many swap operations, which are relatively complicated in the linked list structure. 

Solution:

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        // find the middle point
        ListNode slow = head;
        ListNode fast = head;
        
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        ListNode leftHead = head;
        ListNode rightHead = slow.next;
        
        slow.next = null;
        
        // recursively merge
        leftHead = sortList(leftHead);
        rightHead = sortList(rightHead);
        
        ListNode mergeHead = merge(leftHead, rightHead);
        
        return mergeHead;
    }
    
    private ListNode merge(ListNode leftHead, ListNode rightHead) {
        ListNode newHead = new ListNode(0);
        ListNode curr = newHead;
        
        while (leftHead != null || rightHead != null) {
            if (leftHead == null) {
                curr.next = rightHead;
                break;
            }
            
            if (rightHead == null) {
                curr.next = leftHead;
                break;
            }
            
            if (leftHead.val <= rightHead.val) {
                curr.next = leftHead;
                leftHead = leftHead.next;
                curr = curr.next;
            } else {
                curr.next = rightHead;
                rightHead = rightHead.next;
                curr = curr.next;
            }
        }
        
        return newHead.next;
    }
}

Summary:
The take-away message for this problem is to be very familiar with common sorting algorithms.