создание сортировки слияния, которая принимает LinkedList в качестве входных данных

Question

Вот некоторые из моего кода

listnode *mergesort(struct listnode *list){ 
    struct listnode *L, *R, *head; 
    int i = 0; 
    head = list; 
    while (list->next != NULL){ 
     if (i%2 == 0){    //it splits the linkedlist into 2 segments 
            //it adds the elements in the linked list           
            // alternatively. 
            //to a linked list R & L 
      L=list->next; 
      list->next = L->next; 
      i=i+1; 
     } 
     else{ 
      R= list->next; 
      list->next = R->next; 
      i=i+1; 
     } 
     list = list->next; 

    } 
    MergeLists(mergesort(L),mergesort(R)); 
} 

Я постоянно получаю ошибку сегментации и не могу понять, что проблема есть.

Answer 1

Во-первых, то, что делает ваш «подсчет», - это перемещение left на единицу, когда число равно, и делает то же самое с right, когда число нечетное. Не говоря уже о том, что left и right неинициализированы, если в списке есть только один элемент, а последняя строка цикла может привести к разыменованию нулевого значения.

Во-вторых, вам нужно каким-то образом пометить конец списка left, иначе ваш слияние будет делать то же самое снова и снова, пока вы не переполните стек.

Мы можем сделать это, установив последний указатель в левой половине равным NULL. Имейте в виду, что MergeLists придется исправить все это, чтобы снова сделать один хороший список.

попробовать что-то вроде этого:

listnode *mergesort(listnode *list) { 
    listnode *left = list, *right = list, *prev, *end = list; 

    if (list == 0) { return list; } 

    // move right once for every two we move end, so that we divide the middle 
    while (end != 0) { 
    end = end->next; 
    prev = right; // keep track of the node before the start of right 
    right = right->next; 

    if (end != 0) { 
     end = end->next; 
    } 
    } 


    if (left->next == right) { 
    // TODO swap items if necessary 
    return left; 
    } 

    prev->next = 0; // split the list 
    left = mergesort(left); 
    right = mergesort(right); 
    // TODO join left and right by calling MergeLists or whatever 
    return left; 
} 

Схема указателей на работе:

prev->next = 0 removes -----| 
          v 
list -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] 
left ----^     ^
right -------------------------| 

Answer 2

Две вещи, которые я заметил: 1. int i = 0; значит, я всегда буду ровным. Является ли значение «i» значением в узле списка? 2. вернуть MergeLists (L, R); находится внутри оператора while, поэтому цикл будет завершен.