# [Three-way Quick Sort] C++ beats 96%

• ``````class Solution {
private:
pair<ListNode*, ListNode*> sortList(ListNode* head, ListNode* tail) {
int val = head->val;

ListNode *it = head->next, *nexit = nullptr;
ListNode *lessit = nullptr, *equalit = head, *moreit = nullptr;

while (it != tail->next) {
nexit = it->next;
if (it->val == val) {
equalit->next = it;
equalit = equalit->next;
} else if (it->val < val) {
if (!lessit) {
lessit = it;
} else {
lessit->next = it;
lessit = lessit->next;
}
} else {
if (!moreit) {
moreit = it;
} else {
moreit->next = it;
moreit = moreit->next;
}
}
it = nexit;
}

equalit->next = nullptr;
pair<ListNode*, ListNode*> upperhalf, lowerhalf, res;

res.second = equalit;
lessit->next = nullptr;
upperhalf = sortList(lesshead, lessit);
res.first = upperhalf.first;
}
moreit->next = nullptr;
lowerhalf = sortList(morehead, moreit);
res.second = lowerhalf.second;
equalit->next = lowerhalf.first;
}
return res;
}

public:
ListNode* sortList(ListNode* head) {
ListNode *tail = head;
while (tail->next) tail = tail->next;

pair<ListNode*, ListNode*> range = sortList(head, tail);
return range.first;
}
};
``````

• @HaoxiangXu I wonder why nobody actually reads the description of the problem. It clearly says "constant space complexity". Recursive is definitely not.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.