C语言 交换单向链表中的节点
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15315914/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Swap nodes in a singly-linked list
提问by CodeRat
I am trying to swap two nodes. For example if the nodes are aand bI am passing the pointers(a-1)->nextand (b-1)->nextwhich are basically nodes aand b.
我正在尝试交换两个节点。例如，如果节点是a，b我正在传递指针(a-1)->next，(b-1)->next而它们基本上是节点a和b.
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;
}
What am I doing wrong? When I am trying to print the nodes after calling the function it's an infinite loop. Please help.
我究竟做错了什么？当我在调用函数后尝试打印节点时，它是一个无限循环。请帮忙。
回答by Grijesh Chauhan
Why Infinite loop?
为什么是无限循环？
Infinite loop is because of self loop in your list aftercalling swap()function. In swap()code following statement is buggy.
无限循环是因为调用函数后列表中的自循环swap()。在swap()代码中，以下语句有问题。
(*b)->next = (temp1)->next;
Why?: Because after the assignment statement in swap()function temp1's next starts pointing to bnode. And node[b]'s next point to itself in a loop. And the self loopis reason for infinite loop, somewhere in your code where you traverse linked list.
为什么？: 因为在swap()functiontemp1的 next 中的赋值语句之后开始指向b节点。Andnode[b]的 next 在循环中指向自身。而self 循环是无限循环的原因，在你遍历链表的代码中的某个地方。
Below I drawn to show how swap()works step-by-step. May be this help you to understand your error:
下面我画了swap()一步一步地展示如何工作。可能这有助于您了解您的错误：
You didn't mention but I am assuming linked list having following relation between aand b: (read red comments)
你没有提到，但我假设链表在a和之间有以下关系b:(阅读红色评论）
(step-1):
（第1步）：
+----+----+----+ +---+----+----+
| one |----->| two |
+----+----+----+ +---+---+-----+
^ ^ ^ ^
| | | |
| *a | *b
| |
temp1 temp2, temp3 "after assignment to temp variables"
(step-2): ^
|
*a = *b | *a "<--- next step"
(step-3):The buggy statement
（第 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"
See (temp1)->next;is actually band you are assigning (*b)->next = (*b)by doing (*b)->next = (temp1)->next;hence adding a self loop.
See (temp1)->next;is 实际上b，您正在分配(*b)->next = (*b)，(*b)->next = (temp1)->next;因此添加了一个自循环。
(step-4):
I think with the diagram you can easily understand what last two lines of your swap()code are doing:
（第 4 步）：
我认为通过图表您可以轻松了解swap()代码的最后两行在做什么：
temp2 = temp1;
(temp2)->next = temp3->next;
Following is my diagram for this two lines:
以下是我对这两行的图表：
temp2 = temp1;
+----+----+----+ +---+----+----+ <---|
| one | | two |-----| "<--- Self loop"
+----+----+----+ +---+---+-----+
^ ^ ^ ^
| | | |
| | *b *a
| |
temp2 = temp1; temp3
(step-5):Even last line of your function swap()left loop as below:
（第 5 步）：即使是函数的最后一行也swap()左循环，如下所示：
(temp2)->next = temp3->next; " last line of your code"
+----+----+----+ +---+----+----+ <---|
| one |----->| two |-----| "<-- Self loop"
+----+----+----+ +---+---+-----+
^ ^ ^ ^
| | | |
| | *b *a
| |
temp2 = temp1; temp3
So loop still there at twonode so infinite loop.
所以循环仍然在two节点处无限循环。
How to swap two nodes in single linked list?
如何交换单链表中的两个节点？
One way is swap node's data instead of swapping node's position it self in linked list (as I commented to your question). But you wants to swap node'sposition in list.
Well this good! if node data size is larger, that time its better to swap node's position rather then swap node's data(swapping data will be bad choice)
一种方法是交换节点的数据，而不是交换节点在链表中的位置（正如我对您的问题的评论）。但是您想交换节点在列表中的位置。
嗯，这很好！如果节点数据较大，那么此时最好交换节点的位置而不是交换节点的数据（交换数据将是不好的选择）
Because you having single linked list, to swap any two arbitrary nodes in list you needthere previous node addressestoo. (this is the point you don't consider in your swapping logic)
因为你有单链表，掉在列表中，您任意两个节点需要有一个节点的地址了。（这是您在交换逻辑中不考虑的一点）
WHY need previous pointers?:
Suppose after some successful insert(push) operations, your list becomes as follows:
为什么需要以前的指针？：
假设在一些成功的插入（推送）操作之后，你的列表变成如下：
0 <--------TOP - "head"
9 <--p
2
6 <--q
5
A horizontal diagram- Suppose you want to swapsay two nodes (q)and (p):
水平图 - 假设您想交换两个节点(q)和(p)：
+---+ +---+ +---+ +---+ +---+
| 0 |--->| 9 |--->| 2 |--->| 6 |--->| 5 |---
+---+ +---+ +---+ +---+ +---+ |
^ ^ ^ null
| | |
| (q) (p)
(head)
As I said, to swap we need previous pointers. You need to think about following
(In theory, I am writing for specific nodes (p)and (q)just to keep explanation simple. but my implementation is quit general):
正如我所说，要交换我们需要先前的指针。您需要考虑以下内容
（理论上，我正在为特定节点编写代码(p)，(q)只是为了保持解释简单。但我的实现是通用的）：
In list previous pointers:
在列表之前的指针中：
node[0] points to node[9] that is (q), and
node[2] points to node[6] that is (p)
And
和
node[9] points to node[2]
node[6] points to node[5]
NOTICE:If you want to swap two nodes say node[ 9 ]and node[ 6 ]then you should use pointers of the nodes previous to these two nodes.
For example: two swap node[ 9 ]and [ 6 ], you also need to change next pointer of node[ 0 ]and next pointer of node[ 2 ]in above diagram.
注意：如果你想交换两个节点node[ 9 ]，node[ 6 ]那么你应该使用这两个节点之前的节点的指针。
例如：两个交换node[ 9 ]和[ 6 ]，你还需要改变上图中的next指针node[ 0 ]和next指针node[ 2 ]。
How would be the list after swapping this two nodes?
交换这两个节点后，列表会如何？
+---+ +---+ +---+ +---+ +---+
| 0 |--->| 6 |--->| 2 |--->| 9 |--->| 5 |---
+---+ +---+ +---+ +---+ +---+ |
^ ^ ^ null
| | |
| (p) (q)
(head)
What is now in previous nodes [o]and [2]?
After swapping, In list previous pointers
现在在以前的节点[o]和[2]?
交换后，在列表中以前的指针
node[0] points to node[6] that is (q), and
node[2] points to node[9] that is (p)
And
和
node[9] points to node[5]
node[6] points to node[2]
So if you want to swap two nodes; there immediate previous node also effects and because list is single link list you need previous pointers too.
所以如果你想交换两个节点；前一个节点也有影响，因为列表是单链表，所以你也需要前一个指针。
How to find previous node pointers?
如何找到以前的节点指针？
Suppose you want to swap any two nodes node[p]and node[q]then you can use head pointerto find previous node.
假设您想交换任意两个节点node[p]，node[q]然后您可以使用它head pointer来查找前一个节点。
So swap function syntax(In my implementation) is like:
所以交换函数语法（在我的实现中）是这样的：
void swap(struct stack **head, // head node
struct stack **a, // first candidate node to swap
struct stack **b); // first candidate node to swap
And you will call function like:
您将调用如下函数：
swap(&head, &p, &q);
Definition:(To understand code please read comments I added at almost each line)
定义：（要理解的代码，请阅读我的评论几乎每一行加）
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;
}
In swap()function you can notice that I call a helper function get_prevnd(, );. This function returns address of previous node in list. In The function get_prevnd(, );, first argument is list head and second argument is node for which you are looking for.
在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;
}
And fortunately the code is WORKING :). Below is link for online test of this code. I have tested for various kind of inputs.
幸运的是代码正在运行:)。以下是此代码的在线测试链接。我已经测试了各种输入。
CodePad: To Swap node in single linked list.Please check output.
CodePad：在单链表中交换节点。请检查输出。
And sorry for bad English
抱歉英语不好
回答by David M. Rogers
I was hoping for cut-and-paste code, but didn't find it. If anyone is still interested, this is the answer. I did the brute force analysis of all 3 cases.
我希望剪切和粘贴代码，但没有找到。如果有人仍然感兴趣，这就是答案。我对所有 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;
}
Note: This code works if sp == tp, but assumes you don't have the pathological case where BOTH &s->next == tp && &t->next == sp (starting with cycle).
注意：此代码在 sp == tp 时有效，但假设您没有 BOTH &s->next == tp && &t->next == sp（以循环开头）的病理情况。
回答by user3624969
"KING KHAN"
SwapanyTwoNodeData(int, int);this function take two integer as parameter and swap these
SwapanyTwoNodeData(int, int);此函数以两个整数作为参数并交换它们
node data.
节点数据。
1->2->6->3->4->5
SwapanyTwoNodeData (2,4);
SwapanyTwoNodeData (2,4);
1->3->6->2->4->5
100% Working Function. . . . Enjoy.
100% 工作功能。. . . 享受。
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"<<endl;
}
}
}
