# N(logN) quick sort in-place solution using Java (6ms, beats 90%)

• Quick sort for linked list is a little more confusing and difficult than using merge sort.
Below is the code, someone can optimize it to make it more concise??

``````public class Solution {

// return ListNode[4]
// ListNode[0] -> start of smaller list, null if none
// ListNode[1] -> start of pivot list (contains duplicates of pivot values)
// ListNode[2] -> end of pivot list
// ListNode[3] -> start of bigger list, null if none
// Assume the input head must not be null, already check nullness in the caller
ListNode[] res = new ListNode[4];

ListNode pivotLstEnd = pivotLstStart;

ListNode smallLstStart = null;
ListNode smallLstEnd = null;
ListNode bigLstStart = null;
ListNode bigLstEnd = null;

if(node.val < pivotLstStart.val) {
if(smallLstStart==null)
smallLstStart = node;
else
smallLstEnd.next = node;
smallLstEnd = node;
} else if (node.val > pivotLstStart.val) {
if(bigLstStart==null)
bigLstStart = node;
else
bigLstEnd.next = node;
bigLstEnd = node;
} else {
pivotLstEnd.next = node;
pivotLstEnd = node;
}
}

// must terminate the smallLst and bigLst with null
if(smallLstEnd!=null)
smallLstEnd.next = null;
if(bigLstEnd!=null)
bigLstEnd.next = null;

res[0] = smallLstStart;
res[1] = pivotLstStart;
res[2] = pivotLstEnd;
res[3] = bigLstStart;

return res;
}

// return ListNode[2]
// ListNode[0] -> start non-null node of sorted list
// ListNode[1] -> end non-null node of sorted list
// Note that if none, both ListNode[0] and ListNode[1] are null
// if there is only one node, ListNode[0]==ListNode[1]
ListNode[] res = new ListNode[2];

return res;

ListNode pivotTail = partitionRes[2];

// Below code links the sorted smaller list, pivot list and sorted bigger list
pivotTail.next = bigRes[0];
res[1] = bigRes[1]==null ? pivotTail : bigRes[1];

if(smallRes[0]==null) {
} else {
res[0] = smallRes[0];