Попытка сортировать связанный список, используя функцию слияния?

Question

Я написал функцию для объединения двух отдельных списков. Например, если A = 1 2 3 и B = 3 4 5, и я объединю их оба, я получаю A = 1 2 3 3 4 5 и B = NULL. Теперь я хочу написать функцию, которая сортирует односвязный список, используя алгоритм mergesort (каким-то образом используя мою функцию слияния). Для mergesort, если я не ошибаюсь, мне придется каким-то образом сломать связанный список пополам, а затем выполнить оставшуюся часть работы. У меня есть небольшая схема, написанная о том, как я хочу это делать. Я не уверен, как я буду заниматься делением на данный момент. Любая помощь приветствуется!

  List mergeSort(List L) { 
      if(|L| > 1) { 
       split L into L1 and L2; 
       L1 = mergeSort(L1); 
       L2 = mergeSort(L1); 
       return(merge(L1,L2)); 
      } 
      } 

Моя функция слияния ниже:

void mylist::merge(mylist& b) 
{ 
    if (!this->isSorted() || !b.isSorted()) 
     cout << "error" << endl; 
    Node* ptr1 = b.head; 
    Node* prev_a = NULL; 
    Node* curr_a = head; 
    Node* curr_b = ptr1; 
    while (curr_b) { 
     if (curr_a && head->key < ptr1->key) { 
      prev_a=curr_a; 
      curr_a = curr_a->next; 
     } 
     else { 
      Node* b_next = curr_b->next; 
      curr_b->next = curr_a; 
      if (prev_a) prev_a->next = curr_b; 
      else head = curr_b; // curr_b is first element in 'a' 
       prev_a = curr_b; 
      curr_b = b_next; 
     } 
    return; 
} 

Answer 1

Чтобы разделить список на две половинки, можно использовать два указателя.

Оба указателя начинаются в начале списка. Один указатель перемещается каждые два шага, а другой перемещается на один шаг каждый раз. Когда быстрый указатель достигнет нуля, более медленный указатель укажет на середину списка.

ListNode *fast(head->next), *slow(head); while(fast && fast->next) { fast = fast->next->next; slow = slow->next; }