# LeetCode 148. Sort List

Problem:

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

Solution:

Three way quick sort

```/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
public class Solution {
}

private ListNode quicksort(ListNode pivot) {
if (pivot == null || pivot.next == null)
return pivot;
ListNode prev1 = new ListNode(0), prev2 = new ListNode(0), prev = new ListNode(0);
ListNode dummy1 = prev1, dummy2 = prev2, dummy = prev;
ListNode current = pivot;
while (current != null) {
if (current.val < pivot.val) {
prev1.next = current;
prev1 = prev1.next;
}
else if (current.val > pivot.val) {
prev2.next = current;
prev2 = prev2.next;
}
else {
prev.next = current;
prev = prev.next;
}
current = current.next;
}
prev1.next = prev2.next = prev.next = null;
dummy1.next = quicksort(dummy1.next);
dummy2.next = quicksort(dummy2.next);
current = dummy1;
while (current.next != null) current = current.next;
current.next = dummy.next;
prev.next = dummy2.next;
return dummy1.next;
}
}
```