交换单链表中的节点

我试图交换两个节点。 例如,如果节点是ab我正在传递指针
(a-1)->next(b-1)->next ,它们基本上是节点ab

 void swap(struct stack **a,struct stack **b) { struct stack *temp1 = *a, *temp2 = *b, *temp3 = *b; *a = *b; (*b)->next = (temp1)->next; temp2 = temp1; (temp2)->next = temp3->next; } 

我究竟做错了什么? 当我在调用函数后尝试打印节点时,它是一个无限循环。 请帮忙。

为什么无限循环?

无限循环是因为调用swap()函数列表中的自循环。 在swap()代码中,以下语句是错误的。

 (*b)->next = (temp1)->next; 

为什么? :因为在swap()函数中赋值语句后, temp1的下一个开始指向b节点。 node[b]的下一个指向循环。 自循环无限循环的原因,在代码中的某个位置遍历链表。

下面我将展示swap()如何逐步工作。 可能这有助于您了解您的错误

你没有提到,但我假设链接列表在ab之间有以下关系:( 阅读红色评论

(步骤1):

 +----+----+----+ +---+----+----+ | one |----->| two | +----+----+----+ +---+---+-----+ ^ ^ ^ ^ | | | | | *a | *b | | temp1 temp2, temp3 "after assignment to temp variables" (step-2): ^ | *a = *b | *a "<--- next step" 

(步骤3):车辆声明

 (*b)->next = (temp1)->next; "Change link: (temp1)->next; is `two` node" " *b is `two`, So Self loop" +----+----+----+ +---+----+----+ <---| | one | | two |-----| +----+----+----+ +---+---+-----+ ^ ^ ^ ^ | | | | | | *b *a | | temp1 temp2, temp3 " after assignment to temp" 

(temp1)->next; 实际上是b你正在分配(*b)->next = (*b)(*b)->next = (temp1)->next; 因此添加了一个自循环。

(第4步):
我认为使用图表可以很容易地理解swap()代码的最后两行:

 temp2 = temp1; (temp2)->next = temp3->next; 

以下是这两行的图表:

 temp2 = temp1; +----+----+----+ +---+----+----+ <---| | one | | two |-----| "<--- Self loop" +----+----+----+ +---+---+-----+ ^ ^ ^ ^ | | | | | | *b *a | | temp2 = temp1; temp3 

(步骤5):即使你的函数swap()最后一行左循环如下:

  (temp2)->next = temp3->next; " last line of your code" +----+----+----+ +---+----+----+ <---| | one |----->| two |-----| "<-- Self loop" +----+----+----+ +---+---+-----+ ^ ^ ^ ^ | | | | | | *b *a | | temp2 = temp1; temp3 

所以循环仍然在two节点那么无限循环。

如何在单个链表中交换两个节点?

一种方法是交换节点的数据,而不是交换节点在链表中自己的位置( 正如我对你的问题所评论 )。 但是你想在列表中交换节点的位置。
好吧,这个好! 如果节点数据大小较大,那么它更好地交换节点的位置而不是交换节点的数据( 交换数据将是不好的选择

因为您有单个链表 ,要交换列表中的任意两个任意节点,您也需要 先前的节点地址 。 ( 这是您在交换逻辑中不考虑的一点

为什么需要以前的指针?
假设在一些成功的插入(推送)操作之后,您的列表变为如下:

  0 <--------TOP - "head" 9 <--p 2 6 <--q 5 

水平图 - 假设您要交换说两个节点(q)(p)

 +---+ +---+ +---+ +---+ +---+ | 0 |--->| 9 |--->| 2 |--->| 6 |--->| 5 |--- +---+ +---+ +---+ +---+ +---+ | ^ ^ ^ null | | | | (q) (p) (head) 

正如我所说,交换我们需要先前的指针。 你需要考虑以下
理论上,我正在为特定节点(p)(q)编写,只是为了使解释简单。但我的实现是退出一般 ):

在列表中的前一个指针:

 node[0] points to node[9] that is (q), and node[2] points to node[6] that is (p) 

 node[9] points to node[2] node[6] points to node[5] 

注意:如果要交换两个节点,如node[ 9 ]node[ 6 ] ,则应使用这两个节点之前的节点的指针。
例如:两个交换node[ 9 ][ 6 ] ,您还需要在上图中更改node[ 0 ]下一个指针和node[ 2 ]下一个指针。

交换这两个节点后列表怎么样?

 +---+ +---+ +---+ +---+ +---+ | 0 |--->| 6 |--->| 2 |--->| 9 |--->| 5 |--- +---+ +---+ +---+ +---+ +---+ | ^ ^ ^ null | | | | (p) (q) (head) 

现在在以前的节点[o][2]什么?
交换后,列出以前的指针

 node[0] points to node[6] that is (q), and node[2] points to node[9] that is (p) 

 node[9] points to node[5] node[6] points to node[2] 

所以如果你想交换两个节点; 前一个节点也有效果,因为列表是单链接列表,你也需要先前的指针。

如何找到以前的节点指针?

假设您要交换任意两个节点node[p]node[q]那么您可以使用head pointer来查找上一个节点。

所以交换函数语法在我的实现中 )就像:

 void swap(struct stack **head, // head node struct stack **a, // first candidate node to swap struct stack **b); // first candidate node to swap 

你会称之为以下function:

 swap(&head, &p, &q); 

定义:( 要理解代码,请阅读我几乎每行添加的评论

 void swap(struct stack **head, struct stack **a, struct stack **b){ // first check if a agrgument is null if( (*head) == NULL || // Empty list (*a) == NULL || (*b) == NULL){ // one node is null // Nothing to swap, just return printf("\n Nothing to swap, just return \n"); return; } // find previos nodes struct stack* pre_a = get_prevnd(*head, *a); struct stack* pre_b = get_prevnd(*head, *b); //Now swap previous node's next if(pre_a) pre_a->next = (*b); // a's previous become b's previous, and if(pre_b) pre_b->next = (*a); // b's previous become a's previous //Now swap next fiels of candidate nodes struct stack* temp = NULL; temp = (*a)->next; (*a)->next = (*b)->next; (*b)->next = temp; //change head: if any node was a head if((*head)==(*a)) *head = *b; else if((*head)==(*b)) *head = *a; } 

swap()函数中你可以注意到我调用了一个辅助函数get_prevnd(, ); 。 此函数返回列表中上一个节点的地址。 在函数get_prevnd(, ); ,第一个参数是列表头,第二个参数是您要查找的节点。

 // find previous node function() struct stack* get_prevnd( struct stack* head, struct stack* a ){ if(head == a){ // node[a] is first node return NULL; } struct stack* temp = head; // temp is current node struct stack* pre_a = NULL; while(temp && temp!=a){ //search while not reach to end or the node pre_a = temp; // find previous node temp = temp->next; } if(temp!=a){// node[a] not present in list fprintf(stderr, "\n error: node not found!\n"); exit(EXIT_FAILURE); // bad technique to exit() } return pre_a; } 

幸运的是代码是工作:)。 以下是此代码在线测试的链接。 我测试了各种输入。

CodePad: 在单个链表中交换节点。 请检查输出。

抱歉英语不好

我希望剪切和粘贴代码,但没有找到它。 如果有人仍然感兴趣,这就是答案。 我对所有3个案例进行了蛮力分析。

 // swaps nodes at locations *sp and *tp struct stack *s = *sp; // store locations to prevent overwritten bugs struct stack *t = *tp; if(&t->next == sp) { // order u (tp)-> t (sp)-> s -> ... t->next = s->next; s->next = t; *tp = s; } else if(&s->next == tp) { // order u (sp)-> s (tp)-> t -> ... s->next = t->next; t->next = s; *sp = t; } else { // disconnected u (sp)->s -> ..., v (tp)->t -> ... struct stack *next = s->next; s->next = t->next; t->next = next; *sp = t; *tp = s; } // If you track the end of your list, it be the one pointing to NULL. if(s->next == NULL) { end = &s->next; } else if(t->next == NULL) { end = &t->next; } 

注意:如果sp == tp,此代码有效,但假设您没有BOTH&s-> next == tp &&&t-> next == sp(以循环开始)的病态情况。

  "KING KHAN" 

SwapanyTwoNodeData(int, int); 这个函数取两个整数作为参数并交换它们

节点数据。

 1->2->6->3->4->5 

SwapanyTwoNodeData (2,4);

 1->3->6->2->4->5 

100%的工作function。 。 。 。 请享用。

 void Swap_Any_Two_Locations_data(int x,int x1){ if(head!=NULL){ int count=1,count1=1; Node *temp,*temp1; temp=head; temp1=head; while(temp->next!=NULL && count!=x ){ temp=temp->next; count++; } while(temp1->next!=NULL && count1!=x1){ temp1=temp1->next; count1++; } if(count==x && count1==x1){ int z=0; z=temp->info; temp->info=temp1->info; temp1->info=z; cout<<"Data Swapped"<