# Sort List

## Problem

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

## Example

Given 1->3->2->null, sort it to 1->2->3->null.

## Code - Java

/**
* Definition for ListNode.
* public class ListNode {
*   int val;
*   ListNode next;
*   ListNode(int val) {
*     this.val = val;
*     this.next = null;
*   }
* }
*/
public class Solution {
/**
* @return: You should return the head of the sorted linked list,
* using constant space complexity.
*/
if (head == null) return null;

ListNode dummy1 = new ListNode(0);
ListNode dummy2 = new ListNode(0);
ListNode dummySame = new ListNode(0);
ListNode tail1 = dummy1;
ListNode tail2 = dummy2;
ListNode tailSame = dummySame;

while (ptr != null) {
tail1.next = ptr;
tail1 = tail1.next;
} else if (ptr.val > head.val) {
tail2.next = ptr;
tail2 = tail2.next;
} else {
tailSame.next = ptr;
tailSame = tailSame.next;
}
ptr = ptr.next;
}

tail1.next = null;
tail2.next = null;
tailSame.next = null;

ListNode left = sortList(dummy1.next);
ListNode right = sortList(dummy2.next);

if (dummySame.next != null) {
tailSame.next = right;
} else {
}
ptr = left;
while (ptr != null && ptr.next != null) {
ptr = ptr.next;
}

if (ptr == null) {
}