Обмен двумя узлами

Question

Я хочу обменять два узла связанного списка, и нет, я не хочу менять данные, я хочу изменить ссылки.

вот что я сделал до сих пор.

void swap(student * prev_p, student * p, student * prev_q, student *q) 
{  
     student *tmp=NULL; 

     tmp=p->next; 
     p->next=q->next; 
     q->next=tmp; 

     tmp=prev_p->next; 
     prev_p->next=q; 
     prev_q->next=tmp; 
} 

тогда я называю эту функцию в пузырьке/выбор рода два своп два узла

Probleme это я не знаю, если моя логика работает или нет, второй в моей функции выбора сортировки я только имеют мин указатель и текущий один

Answer 1

Ваш код будет работать только для этого типа цепи:

... -> prev_p -> p -> ... -> prev_q -> q ->... 

или

... -> prev_q -> q -> ... -> prev_p -> p ->... 

Но не будет работать, если у вас есть такие ситуации:

... -> prev_p -> p -> q -> .... 

или

... -> prev_q -> q -> p ->... 

Используя код, вы в конечном итоге с петлей внутри связанного списка в обоих ситуации (... prev_p -> q -> q для первого и ... prev_q -> q -> q для второй ситуации).

Перед изменением next полей prev_p или prev_q вы должны сначала проверить, если это не соответственно q или p иначе вы будете в конечном итоге с неловких ситуаций, описанных выше. Так что ваша вторая часть вашей функции должна быть что-то вроде:

if (prev_q == p){ 
    q->next = p; 
else{ 
    if(prev_q){ 
     prev_q->next = p; 
    }else{ 
     // q has no parent -> q was the head -> p must become new head 
    } 
} 
if (prev_p == q){ 
    p->next = q; 
else{ 
    if(prev_p){ 
     prev_p->next = q; 
    }else{ 
     // p has no parent -> p was the head -> q must become new head 
    } 
} 

EDIT, если р или д может быть глава списка, они не будут иметь родителя. prev_q или prev_p будет NULL (см. Ваш pastebin)

PS: Эта проблема не возникнет, если вы замените данные вместо обмена ссылками. Как вы сказали (в своем описании) вы не хотите менять данные, я дам вам подумать, нужно ли менять тактику или нет.