Попытка сортировать связанный список только путем манипуляции указателями

Question

Я пытаюсь использовать Selection Сортировка, чтобы отсортировать связанный список. Я могу манипулировать указателями связанных списков и не изменять ключи. Я думаю, что у меня есть функциональная логика, но я просто возвращаю исходную несортированную последовательность.

bool nodeSwap(Node* head){ 

    Node* next = head->next; 
    if(next == NULL){ return head;} 
    head->next = next->next; 
    next->next = head; 
    head = next; 
    return next; 
} 
Node* sort_list(Node* head){ 

for(Node* n = head; n->next != NULL; n = n->next){ 
    for(Node* n1 = head->next; n1 != NULL; n1 = n1->next){ 
     if(n-> key > n1->key){ 
      nodeSwap(n); 


      } 
    } 
} 
return head; 
} 

---

EDIT

Хорошо, так что я прошел и добавил еще и какая-то логика, которая на самом деле имеет некоторый смысл в этот раз, и у меня есть функция почти работает ... Только проблема в том, что всегда пропускает сортировку по всем первым двум элементам в списке и не возвращается после сортировки. Любые мысли о том, почему это может произойти?

Node* sort_list(Node* head){ 

Node* curr; 
Node* prev; 

    for(curr = head; curr->next != NULL; curr = curr->next){ 
     if(curr == head){ 
      head = curr->next; 
      curr->next = head->next; 
      head->next = curr; 
      prev = head; 
     } 
    else if(curr->key > curr->next->key){ 
        head = curr->next; 
        curr->next = head->next; 
        head->next = curr; 
        prev = head; 
       } else if(curr -> next -> next != NULL){ 

        prev->next = curr->next; 
        curr->next = prev->next->next; 
        prev->next->next = curr; 

        }else if(head != curr){ 
         prev = prev->next; 
        }else{} 
    } 


return head; 
} 

Answer 1

Попробуйте ввести код, который компилирует и/или задает конкретный вопрос.

линия 3: return head;

в функции, которая должна возвращать булево

Answer 2

Похоже вы передаете п по значению. Если вам необходимо изменить значение п внутри функции, вам необходимо либо сделать его глобальным (Argh) или передать адрес п:

bool nodeSwap(Node** head){ 
    [...] 
} 

Answer 3

один список, или дважды связанный список? Вы упомянули об обмене данными только, но вы не указали определение указателя (только ключ или ключ & указатели данных?),

Если вы хотите поменять содержимое двух узлов, вам необходимо указать указатели на оба узлы в функции nodeSwap,

bool nodeSwap(Node* a, node* b) 
{ 
    if(!a) return false; 
    if(!b) return false; 
    int temp = a->key; 
    a->key = b->key 
    b->key = temp; 
    void* dtemp = a->data; 
    a->data = b->data; 
    b->data = dtemp; 
    return true; 
} 

Если вы хотите поменять местами целые узлы, то вам необходимо предоставить предыдущие указатели, или пойти и найти их (ниже предполагается, дважды связанный список, или где вы видите «пред» вы найдете его),

bool nodeSwap(Node* a, node* b, Node* head) 
{ 
    if(!a) return false; 
    if(!b) return false; 
    Node* ap=NULL, *bp=NULL; 
    //double linked list 
    ap = a->prev; 
    bp = b->prev; 
    //single linked list, get ap (a.previous), 
    if(a!=head) 
     for(ap=head; ap!=a->next;) 
      ap=np->next; 
    //single linked list, get bp (b.previous) 
    if(b!=head) 
     for(bp=head; bp!=b->next;) 
      bp=bp->next; 
    Node* temp; 
    temp = a; 
    //fix a->prev->next, b->prev->next 
    ap->next = b; //was a 
    bp->next = a; //was b 
    //swap a->next, b->next 
    temp = a->next; 
    a->next = b->next; 
    b->next = temp; 
    //swap a->prev, b->prev for double-linked list 
    temp = a->prev; //double linked list 
    a->prev = b->prev; //double linked list 
    b->prev = temp; //double linked list 
    //swap keys, not needed, you moved the Node* 
    return true; 
} 

An d здесь является nodeSwap с обоими указателями,

Node* sort_list(Node* head){ 
    for(Node* n = head; n->next != NULL; n = n->next){ 
     for(Node* n1 = head->next; n1 != NULL; n1 = n1->next){ 
      if(n-> key > n1->key){ 
       nodeSwap(n,n1); 
       //nodeSwap(n,n1,head); 
      } 
     } 
    } 
    return head; 
}