# 20191204

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:
Input: 4->2->1->3
Output: 1->2->3->4

Example 2:
Input: -1->5->3->4->0
Output: -1->0->3->4->5

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
  public ListNode sortList(ListNode head) {
     if (head == null) return null;
     if (head.next == null) return head;
    
    PriorityQueue<Integer> queue = new PriorityQueue();
    queue.offer(head.val);
    while(head.next != null) {
        System.out.println(head.next.val);
        queue.offer(head.next.val);
        head = head.next;
    }
    
    ListNode resultNode = new ListNode(queue.poll());
    ListNode dummy = resultNode;
    while(!queue.isEmpty()) {
       ListNode node = new ListNode(queue.poll());
       dummy.next = node;
        dummy = node;
    }
    
    return resultNode;   
    }

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) 
        return head;
    
    ListNode mid = cutHalf(head); // 2
    
    ListNode left = sortList(head); // 3 -> 1
    ListNode right = sortList(mid); // 4 -> 5
    
    return merge(left, right);
}

/**             o
  * 2 - 1 - 4 - 5
  *     x
  */
  
  1 -> 2 -> 3 -> 4 -> 5
  x    x    x
  x    x     
  
  
public ListNode cutHalf(ListNode node) {
    ListNode prev = null;
    ListNode slow = node;
    ListNode fast = node;
    
    while (fast != null && fast.next != null) {
        prev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    
    prev.next = null;
    
    return slow;
}

public ListNode merge(ListNode left, ListNode right) {
    ListNode dummy = new ListNode(Integer.MIN_VALUE);
    ListNode endNode = dummy;

    while (left != null && right != null) {
        if (left.val < right.val) {
            endNode.next = left;
            left = left.next;
        } else {
            endNode.next = right;
            right = right.next;
        }
        
        endNode = endNode.next;
    }
    
    if (left != null) {
        endNode.next = left;
    }
    
    if (right != null) {
        endNode.next = right;
    }
    
    return dummy.next;
}

https://leetcode.com/problems/middle-of-the-linked-list/

class Solution {
    public ListNode middleNode(ListNode head) {
    if (head == null) return null;
    
    int length = getLength(head);
    // odd even
    
    int halfLen = length / 2;
    
    // 2
    while (halfLen != 0) {
        head = head.next; // 2 3
        halfLen--; // 0
    }
    
    return head;
  } 
  
  public int getLength(ListNode head) {
    int length = 0;
    
    while (head != null) {
      length++;
      head = head.next;
    }
      
    return length;
  }
}