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;
}
}
```

One thought on “LeetCode 148. Sort List”

1. Wow, fantastic blog layout! How long have
you been blogging for? you made blogging look easy. The overall look of
your site is magnificent, as well as the content!