# 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
`/** * 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; }`