Merge sort on a linked list

Sort a linked list

Using the merge sort based on the 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; 
}