Merge sort on a linked list

  • find the middle point by using fast and slow pointer
  • cut the linked list into two parts: left: [begin, mid], right : [mid + 1, end]
  • recursively sort left and right
  • merge the results from left and right
Merge sort base on linked list solution screenshot
/**
* class LLNode {
* public:
* int val;
* LLNode *next;
* };
*/
void merge_sort(LLNode* left, LLNode* right){
if (left == right) return;
if (left -> next = right){
if (left -> val > right -> val){
swap(left -> val, right -> val);
}
return;
}
auto slow = left, fast = left;
while (fast -> next && fast -> next -> next){
slow = slow - > next;
fast = fast -> next -> next;
}
merge_sort(left, slow);
merge_sort(slow -> next, right);
auto l = left, r = slow -> next;
/*
11
7 9 10
*/
while (true){
if (l -> val > r -> val){
swap(l -> val, r - > val);
}
if (l == slow) break;
l = l -> next;
}
}
LLNode* solve(LLNode* node) {
if (node == nullptr) return nullptr;
auto begin = node;
auto curr = node;
auto end = node;
while (curr){
end = curr;
curr = curr -> next;
}
merge_sort(begin, end);
return node;
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store