我试图做一个swapNode ，可以采取任何两个节点交换它们的功能。 我做了，如果他们至少2个节点远的作品的算法，但我似乎无法拿出一个算法，如果他们互相靠近，将工作。
这是我写的，到目前为止：
void swapNode(call * &head, call * &first, call * &second){
call * firstPrev = NULL;
call * secPrev = NULL;
call * current = head;
//set previous for first
while((current->next != first) ){
current = current->next;
}
firstPrev = current;
current = head;
//set previous for second
while((current->next != second) ){
current = current->next;
}
secPrev = current;
current = second->next;
//set firstPrev-> next to second
firstPrev->next = second;
//set secPrev->next to first
secPrev->next = first;
//set second->next = first->next
second->next = first->next;
//set first->next to current
first->next = current;
current = head;
while(current->next != NULL){
cout << current->number << endl;
current = current->next;
}
cout << current->number << endl;
}
编辑：我现在有这个作为我掉一部分，但它似乎仍然没有正常工作
//swap firstPrev-> next with second->next
tmp = firstPrev->next;
second->next = firstPrev->next;
second->next = tmp;
//swap swap first->next with second->next
tmp = first->next;
second->next = first->next;
second->next = tmp;
EDIT2：这一次似乎没有任何工作，我得到一个赛格故障。
//swap previous's->next
tmp =firstPrev->next;
secPrev->next = firstPrev->next;
secPrev->next = tmp;
//swap swap first->next with second->next
tmp = first->next;
second->next = first->next;
second->next = tmp;
Answer 1:
假设我们有：
Node1 -> Node2 -> Node3 -> Node4 -> Node5
要交换两个节点，需要交换的next他们每个人的面前的那些价值观，也是next要交换节点的值。
所以交换，也就是说，2,3两个节点的，这样就换Node1->next与Node2->next ，和Node2->next与Node3->next 。 这将工作，即使他们是对彼此相邻（或者即使是同一节点）。 例如：
交换Node1->next和Node2->next
Node1->next = Node3
Node2->next = Node2
交换Node2->next与Node3->next
Node2->next = Node4
Node3->next = Node2
这出来的：
Node1 -> Node3 -> Node2 -> Node4 -> Node5
交换！
正如您可在评论部分指出，如果任何东西交换节点1，你必须为链表设置一个新的头。
在回答这个问题的编辑：
您的交换几乎是正确的代码。 但是，你需要换用secPrev的首页前页。 正巧在我的例子中，我们是交换节点的一个next值的两倍，因为他们是彼此相邻。 但是，从逻辑上讲，我们希望交换的next了前两者的s，然后交换next的实际节点秒。 试试这个：
//swap firstPrev-> next with secPrev->next
tmp = firstPrev->next;
secPrev->next = firstPrev->next;
secPrev->next = tmp;
//swap swap first->next with second->next
tmp = first->next;
second->next = first->next;
second->next = tmp;
如果你得到一个段错误，请检查TMP变量 - 它可能是分配或删除错误的地方。 你从哪里得到的段错误？
Answer 2:
在最真实的生活场景，交换价值将是最好的解决办法：
void swapNode(call * &head, call * &first, call * &second) {
// swap values, assuming the payload is an int:
int tempValue = first->value;
first->value = second->value;
second->value = tempValue;
}
如果这是不允许的，那么你想要做一个类似风格的交换 - >未来，而不是 - >价值的组成部分。 再另做掉在firstPrev->下一个和secondPrev->下一个组件。 当心特殊情况下的第一或第二==头。
Answer 3:
你将不得不也换了next上一个节点的组成部分，否则链表不会保持连接在一起。 请注意，我的结构被称为node 。
int swapNode( node *&head * &first, node * &second)
{
//first we will declare the
//previous of the swapping nodes
node *firstprev=NULL;
node*secprev=NULL;
node*current=head;
//set previous first
while(current->next!=first)
{
current=current->next;
}
firstprev=current;
//seting 2nd previous
while(current->next!=second)
{
current=current->next;
}
// swap values, assuming the payload is an int:
int tempValue = first->value;
first->value = second->value;
second->value = tempValue;
//swaping next of the nodes
firstprev->next=second;
secprev->next=first;
return;
}
Answer 4:
经验法则：“从指针总是单独的数据和永不掉球，只有数据！”。 请互换明确不使用的memcpy（），从而可避免对齐问题。 它会导致在算法复杂度方面没有性能损失，但使你的代码更安全。
Answer 5:
这里P1被swaped第一点，P2被swaped第二个节点。 而prevnode是以前P2的节点
temp=head;
while(temp!=NULL){
if(temp->link==p1){
temp->link=p2;
prevnode->link=p2->link;
p2->link=p1->link;
t=p1->link;
while(t!=prevnode)
t=t->link;
cout<<" YES";
cout<<"["<<t->num<<"] ";
p1->link=prevnode->link;
prevnode->link=p1;
temp=p1;
}//if_
cout<<" "<<temp->num;
temp=temp->link;
}
Answer 6:
虽然我不是100％肯定的回答应该包含引用节点指针（或指针的指针），然后这应该处理的情况下，当一个节点是链表的头也是如此。
void swapNodes(node *&first, node *&second)
{
node *t = second->next;
second->next = first->next;
first->next = t;
t = second;
second = first;
first = t;
}
然后，你可以调用它，例如：
swapNodes(head, secPrev->next);
要么
swapNodes(firstPrev->next, head);
要么
swapNodes(firstPrev->next, secPrev->next)
它应该自动地工作。
编辑：
swapNodes可能更加可读：
void swapNodes(node *&first, node *&second)
{
std::swap(first->next, second->next);
std::swap(first, second);
}
Answer 7:
如果你想知道在简单的C链表交换两个节点的所有方法才访问此链接：
http://sahilalipuria.wordpress.com/2013/01/21/swapping-two-nodes-of-a-singly-linked-lists-set-2/
Answer 8:
void swap()
{
struct node *temp=0,*nxt,*ptr;
ptr=head;
int count=0;
while(ptr)
{
nxt=ptr->link;
if(nxt)
{
if(count==0)
head=nxt;
count++;
ptr->link=nxt->link;
nxt->link=ptr;
if(temp!=NULL)
temp->link=nxt;
temp=ptr;
if(ptr->link==NULL)
break;
ptr=nxt->link->link;
}
}}
Answer 9:
谢谢大家对你的答案！ 我也知道这个问题已经差不多两年前问和答案早就被接受，但我已经受了一点答案混淆。 因此，尽管可能提问不关心新的答案，我想补充我的版本，以防其他读者感到困惑，以及和记录我自己的方法。 其中一些可能已经作为注释更加贴合，但我没有信誉发表评论，但。
首先，不管多久我看它 - 在白板上或在调试器 - 我似乎无法避免与第一节点的循环结束了，即指向自身，如果我不使用条件的情况下进行区分的节点是相邻的，而不是，甚至与抽象的步骤或从由Smashery目前公认的答案的具体代码。 我已经四处张望了一下在互联网上找到了目前公认的答案的代码风格，以避免这样的条件，但对我来说，这是令人惊讶的棘手避免和我的搜索没有打开了这样的解决方案（除非我错了关于所提出的一个可能是不正确的）。 如果有一些聪明的表达，将产生时，他们是相邻的，并且第一节点的继任者的地址时，他们都没有，那么把条件就不再需要第一个节点的地址，因为找出第二个节点的新的继任者是什么（显然）必要把条件。
其次，我对连续分配到接受的答案为其他评论家相同的变量相同的问题。 我希望我不是非常密集这里，但在序列相同的变量指定不同的价值，除非也许在副作用的情况下，我只是似乎从来没有离开变量与任何其它的值比上一次分配，不管我考虑什么节点的配置，从而使以前的任务显然是多余的。 如果我错了，并且做法实际上会解决这个问题，那么我会一直能够消除在下面的代码，我试图摆脱掉，当我第一次看到在互联网上解决最后一个条件交换节点没有特殊壳体的相邻节点。 我不太清楚，但它听起来像Smashery故意留下那些重复的任务了逻辑的严密性，并更好地说明该过程 - 我可能误解了，虽然。
第三，这和其他的网站我经常看到其他答案的声明重申，这是更好地交换节点的内容，而不是指针。 当然，在简单的整数，在到目前为止的例子的情况下，不会产生明显缩短，简单的代码。 然而，当我们讨论链表包含的节点整数它通常是作为一个独立的在一个更加复杂和通用容器的支持数据结构。 因此，我不认为交换节点的内容是真的那么容易，至少如果数据结构的实现不能对容器的项目的复制语义假设。 此外，能够交换周围像那个节点的内容意味着，我认为链表有这些节点内容的所有权，否则代码的链接列表的方法之外可能会持有这些节点，其值的对象引用突然他们多次改变。
我承认，不过，这可能依赖于容器的语义。 对于阵列，交换方法可以预期的引用下面的值更改为阵列的某些索引。 这将意味着，引用不是指一个特定的对象，但在容器中的位置是一个可以索引。 如果我们考虑一个链表作为一种手段，只订购一组对象，其中有链表以外的使用中，用户可能会希望交换操作，只交换位置，而不是内容。
想象一下，例如，链表代表型“车”的对象。 每节车厢都有一个所有者和所有者通过一个指向它引用了他们的车。 现在假设链表表示一组车计划于被服务在汽车经销商检查的顺序。 如果我们换两个节点的内容，以两辆车交换时间表插槽，并通过交换它们的内容做到了，那么服务实际上会发生在新的，正确的顺序 - 但人们也最终会突然拥有不同的车！ （我不介意与特斯拉交换，但是，因为我只是开着花冠）。
如果链表是，如在阵列的例子中，基于索引的语义，则在该节点的位置可以简单地表示其中汽车装载到船舶运输的顺序。 在这一点上，汽车没有任何业主，我们真正关心他们是什么插槽。然后，我想这真的不会伤害到换出汽车，即由节点所引用的对象的内容。
终于到了代码。 正如我上面所说的，我还没有能够避免特殊壳体相邻节点。
首先，一个辅助方法的定义：
int find_node(int v, node* root, node** n, node** pn) {
int i = 0;
for (*n = root; *n != NULL && (*n)->v != v; ++i) {
*pn = *n;
*n = (*n)->next;
}
return i;
}
该方法通过其值找到的节点。 返回的整数是链表的节点的从零开始的位置（称之为它的索引，如果你喜欢）。 我发现检测通过邻接的位置，而不是指针比较，更具有可读性。 列表的开始是根。 该方法将n设置为指向包含所传递的值的节点。 在PN，该方法存储n的前身。
下面是实际的交换：
void swap_nodes(node **root, int v1, int v2) {
if (v1 == v2) return;
node *n1, *n2, *pn1, *pn2;
int p1 = find_node(v1, *root, &n1, &pn1);
int p2 = find_node(v2, *root, &n2, &pn2);
if (p1 > p2) {
std::swap(n1, n2);
std::swap(pn1, pn2);
std::swap(p1, p2);
}
if (p1 == 0) *root = n2;
else pn1->next = n2;
node* nn1 = n1->next;
n1->next = n2->next;
if (p2 - p1 > 1) {
n2->next = nn1;
pn2->next = n1;
} else {
n2->next = n1;
}
}
我很抱歉，我已经改变了OP的方法一点的签名。 我发现它更方便在交换节点的值传递，而不是节点指针。 如果您在节点指针只有各节点通过，你会做另一个穿越找到与此解决方案，这感觉有点别扭对我的前辈。 如果我们不能被这些值区分节点，例如值不是唯一的，我们需要指针的节点，虽然。
正如上面find_node的解释，我们先找到位置，节点，以及通过v1和v2传递给swap_nodes节点值前辈。 如果交换到所述第二节点之前首先出现的第一和第二节点中的值的所有交换。 这不是多的代码这样做，减少了特殊外壳，并使其更容易一点想象。
现在，我们只剩下两个条件句，没有这似乎微不足道避免。 如果所述第一节点在链接列表的头部，即在零位置中，根需要指向第二个节点。 否则，第一个节点的前任将指向第二个节点。
需要第一节点的后继的先前值被记住，如果节点是不相邻的。 于是，第一个节点的继任者被设置为第二个节点的当前接班人。 这是适用于所有情况下，唯一的变化：第一个节点是第二个节点的旧继任者的新的继任者是唯一可以肯定的和有益的实施这一交换时，为了记住的指针操作及其顺序与开始。
最后，如果节点的位置被一个以上的不同，他们不相邻。 然后，第二个节点的新的继任者将成为第一个节点的老继任者 - 远保存上面 - 而现在的第二个节点的前身指向第一个节点。 如果它们是相邻的，也有节点之间没有节点交换需要更新，所以简单地连接第二个节点到第一是所有剩下要做。
文章来源: Swapping Nodes on a single linked list
