交换两个节点

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）。

之前改变prev_p的next字段或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 
    } 
} 

编辑如果P或Q可以在列表的头部，他们将没有父。 prev_q或prev_p然后将为空（请参阅您的pastebin）

PS：如果您将交换数据而不是交换链接，则不会发生此问题。正如你所说（在你的描述中）你不想交换数据，我会让你考虑是否需要改变战术。