C++ 在单个链表上交换节点

Swapping Nodes on a single linked list

提问by Reti

I am trying to make a swapNodefunction that can take any two nodes and swap them. I've made an algorithm that works if they're at least 2 nodes away, but I can't seem to come up with an algorithm that will work if they are closer to each other.

我正在尝试创建一个swapNode可以接受任意两个节点并交换它们的函数。我已经制定了一个算法，如果它们至少相距 2 个节点，则该算法有效，但我似乎无法提出一种算法，如果它们彼此靠近，则该算法将有效。

Here's what I wrote so far:

这是我到目前为止所写的内容：

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;
}

EDIT: I now have this as my swap part, but it still doesn't seem to work correctly

编辑：我现在把它作为我的交换部分，但它似乎仍然不能正常工作

//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: This one doesn't seem to work either, I get a seg fault.

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;

回答by Smashery

Say we have:

假设我们有：

Node1 -> Node2 -> Node3 -> Node4 -> Node5

To swap two nodes, you need to swap the nextvalues of the ones before each of them, and also the nextvalues of the nodes you want to swap.

要交换两个节点，您需要交换next每个next节点之前的值，以及要交换的节点的值。

So to swap, say, Node2 and Node3, you effectively have to swap Node1->nextwith Node2->next, and Node2->nextwith Node3->next. That will work, even if they're right next to each other (or even if it's the same node). For example:

因此，要交换，也就是说，2,3两个节点，您有效得交换Node1->next用Node2->next，并Node2->next用Node3->next。这将起作用，即使它们彼此相邻（或者即使它们是同一个节点）。例如：

Swap Node1->nextand Node2->next

交换Node1->next和Node2->next

Node1->next = Node3
Node2->next = Node2

Swap Node2->nextwith Node3->next

交换Node2->next与Node3->next

Node2->next = Node4
Node3->next = Node2

This comes out as:

结果如下：

Node1 -> Node3 -> Node2 -> Node4 -> Node5

Swapped!

交换了！

As unwind noted in the comments section, if swapping Node1 with anything, you'll have to set a new head for the linked list.

正如评论部分中的 unwind 所指出的那样，如果将 Node1 与任何东西交换，则必须为链表设置一个新头。

---

---

In response to the edit of the question:

针对问题的编辑：

Your code for swapping almostright. However, you need to swap the firstPrev with secPrev. It just so happened in my example that we were swapping one of the node's nextvalues twice, because they were next to each other. But logically, we want to swap the nexts of the two previous ones, and then swap the nexts of the actual nodes. Try this:

您的交换代码几乎正确。但是，您需要将 firstPrev 与 secPrev 交换。在我的示例中恰好发生了我们交换节点next值之一两次的情况，因为它们彼此相邻。但从逻辑上讲，我们希望交换next前两个next节点的s，然后交换实际节点的s。尝试这个：

//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;

If you're getting a segfault, check the tmp variable - it could be an error of allocation or deletion somewhere. Where do you get the segfault?

如果您遇到段错误，请检查 tmp 变量 - 这可能是某个地方的分配或删除错误。你从哪里得到段错误？

回答by Jeff Meatball Yang

In most real-life scenarios, swapping the values will be the best solution:

在大多数现实生活场景中，交换值将是最好的解决方案：

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;
}

If that's not allowed, then you want to do a similar-style swap on the ->next instead of the ->value component. And then do another swap on the firstPrev->next and secondPrev->next components. Watch out for the special case where first or second == head.

如果这是不允许的，那么您希望在 ->next 而不是 ->value 组件上进行类似样式的交换。然后对 firstPrev->next 和 secondPrev->next 组件进行另一次交换。注意 first 或 second == head 的特殊情况。

回答by ExtraSmart

You will have to also swap the nextcomponent of the previous node, otherwise the linked list will not remain joined together. Note that my struct is called node.

您还必须交换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; 
}

回答by Usman Raza

Here p1 is the 1st node to be swaped, p2 is 2nd node to be swaped. And prevnode is the node that is previous of p2

这里 p1 是要交换的第一个节点，p2 是要交换的第二个节点。而 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;   
    }

回答by psihodelia

Rule of thumb: "Always separate data from pointers and never swap pointers, only the data!". Make swap explicit without using memcpy(), thus you can avoid alignment problems. It causes no performance penalty in terms of algorithmic complexity, but makes your code more readable and safe.

经验法则：“始终将数据与指针分开，从不交换指针，只交换数据！”。在不使用 memcpy() 的情况下使交换显式，从而可以避免对齐问题。它不会在算法复杂性方面造成性能损失，但会使您的代码更具可读性和安全性。

回答by amit singh

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;
 }

} }

} }

回答by Tomek

While I am not 100% sure the answer should involve references to node pointer (or pointers to pointers) and this should then handle a case when one of the nodes is the head of list as well.

虽然我不是 100% 确定答案应该涉及对节点指针（或指向指针的指针）的引用，并且这应该处理节点之一也是列表头的情况。

void swapNodes(node *&first, node *&second)
{
  node *t = second->next;
  second->next = first->next;
  first->next = t;
  t = second;
  second = first;
  first = t;
}

Then you can call it for example:

然后你可以调用它，例如：

swapNodes(head, secPrev->next);

or

或者

swapNodes(firstPrev->next, head);

or

或者

swapNodes(firstPrev->next, secPrev->next)

and it should work automagically.

它应该自动工作。

EDIT:

编辑：

swapNodes could be even more readable:

swapNodes 可能更具可读性：

void swapNodes(node *&first, node *&second)
{
  std::swap(first->next, second->next);
  std::swap(first, second);
}

回答by user2880576

Thank you everyone for your answers! I do realize that this question has been asked almost two years ago and an answer long been accepted, but I have been a bit confused by the answers. Thus, despite the questioner probably not caring about new answers, I would like to add my version, in case other readers were confused as well and to document my own approach. Some of this may have been more fitting as comments, but I do not have the reputation to comment, yet.

谢谢大家的回答！我确实意识到这个问题已经在差不多两年前被问到了，并且早就被接受了，但我对这些答案感到有些困惑。因此，尽管提问者可能不关心新的答案，但我想添加我的版本，以防其他读者也感到困惑，并记录我自己的方法。其中一些可能更适合作为评论，但我还没有评论的声誉。

First, no matter how often I look at it - on the whiteboard or in the debugger - I cannot seem to avoid ending up with a loop in the first node, i.e. pointing to itself, if I do not use a conditional to distinguish between cases of nodes being adjacent and not, even with the abstract steps or the concrete code from the currently accepted answer by Smashery. I have looked around a bit on the Internet to find code in the style of the currently accepted answer to avoid such a conditional, but to me it is surprisingly tricky to avoid and my searches have not turned up such a solution (unless I am wrong about the proposed one possibly being incorrect). If there was some clever expression that would yield the first node's address when they are adjacent and the first node's successor's address when they are not, then that conditional would not be needed, because figuring out the second node's new successor is what (apparently) necessitates that conditional.

首先，无论我多久看一次——在白板上或在调试器中——如果我不使用条件来区分情况，我似乎无法避免在第一个节点中以循环结束，即指向自身节点是相邻的而不是相邻的，即使是来自 Smashery 当前接受的答案的抽象步骤或具体代码。我在互联网上环顾了一下，以当前接受的答案的风格找到代码以避免这种条件，但对我来说，避免这种情况非常棘手，而且我的搜索没有找到这样的解决方案（除非我错了关于提议的可能不正确）。如果有一些巧妙的表达式可以在它们相邻时产生第一个节点的地址，而当它们不相邻时产生第一个节点的后继地址，

Second, I have the same question about the consecutive assignments to the same variables in the accepted answer as other commentators. I hope I am not being extremely dense here, but assigning different values to the same variable in sequence, unless perhaps in case of side-effects, to me just never seems to leave the variable with any other value than the last assignment, no matter what configuration of nodes I consider, and thus makes the previous assignments apparently redundant. If I am wrong about that and that approach would in fact solve this problem then I would have been able to eliminate the last conditional in the code below, which I was trying to get rid off when I first looked on the Internet for a solution to swapping nodes without special-casing adjacent nodes. I am not quite sure, but it sounded like Smashery purposefully left those repeated assignments out of logical rigor and to better illustrate the procedure - I may have misunderstood, though.

其次，我和其他评论员一样，对在接受的答案中连续分配相同的变量有同样的问题。我希望我在这里不是非常密集，而是按顺序为同一个变量分配不同的值，除非可能出现副作用，对我来说似乎永远不会给变量留下任何其他值而不是最后一次分配，无论我考虑了什么样的节点配置，从而使之前的分配显然是多余的。如果我错了，并且该方法实际上可以解决这个问题，那么我将能够消除下面代码中的最后一个条件，当我第一次在互联网上寻找解决方案时，我试图摆脱它交换节点没有特殊情况下的相邻节点。我不太确定，

Third, on this and other sites I have often seen the statement from other answers repeated that it is better to swap the content of the nodes, rather than the pointers. Of course, in the case of simple integers, as in the examples so far, that does apparently yield shorter, simpler code. However, when we discuss linked lists with nodes containing integers it is usually as a stand-in for the backing data structure of a more complex and generic container. As such, I don't think swapping the contents of the nodes is really that easy, at least if the implementation of the data structure cannot make assumptions about the copy semantics of the container's items. Also, being able to swap around the contents of nodes like that implies to me that the linked list has ownership of the contents of those nodes, because otherwise code outside of the linked list's method might hold references to the objects in those nodes, whose values suddenly change underneath them.

第三，在这个网站和其他网站上，我经常看到其他答案中重复的陈述，即交换节点的内容而不是指针的内容更好。当然，在简单整数的情况下，如目前为止的示例，显然会产生更短、更简单的代码。然而，当我们讨论带有包含整数的节点的链表时，它通常作为更复杂和通用容器的后备数据结构的替代品。因此，我不认为交换节点的内容真的那么容易，至少如果数据结构的实现不能对容器项的复制语义做出假设。此外，能够像这样交换节点的内容对我来说意味着链接列表拥有这些节点的内容的所有权，

I do admit, though, that this might depend on the semantics of the container. For an array, a swap method may be expected to change the value underneath references to a certain index of that array. That would mean that the references are not meant to refer to a specific object, but to a position in a container that one can index. If we consider a linked list as a means to only order a set of objects, which have their use outside of the linked list, a user would probably expect a swap operation to only exchange the position, not the contents.

不过，我承认这可能取决于容器的语义。对于数组，交换方法可能会更改对该数组某个索引的引用下面的值。这意味着引用并不意味着指向特定对象，而是指向容器中可以索引的位置。如果我们将链表视为仅对一组对象进行排序的方法，这些对象在链表之外使用，则用户可能希望交换操作仅交换位置，而不是内容。

Imagine, for example, that the linked list represents objects of type "car". Each car has an owner and that owner references their car through a pointer to it. Now suppose the linked list represents the order a set of cars are scheduled to be serviced for inspection at a car dealership. If we swapped the contents of two nodes, in order to exchange the schedule slots for two cars, and did it by exchanging their contents, then the servicing would in fact happen in the new, right order - but people would also end up suddenly owning different cars! (I wouldn't mind swapping with a Tesla, though, because I am only driving a Corolla.)

例如，想象一下，链表表示“汽车”类型的对象。每辆车都有一个车主，车主通过一个指向它的指针来引用他们的车。现在假设链表表示一组汽车被安排在汽车经销商处进行维修以供检查的顺序。如果我们交换两个节点的内容，以交换两辆车的时间表槽，并通过交换它们的内容来实现，那么服务实际上会以新的、正确的顺序发生——但人们最终也会突然拥有不一样的车！（不过，我不介意换一辆特斯拉，因为我只开卡罗拉。）

If the linked list was, as in the example of the array, based on indexing semantics then the position in the node might simply represent the order in which the cars are loaded onto a ship for transport. At this point, the cars don't have any owners and we really only care what slot they are in. Then, I suppose it really doesn't hurt to swap out cars, i.e. the contents of the objects referenced by the nodes.

如果链表是基于索引语义的，就像在数组的例子中那样，那么节点中的位置可能只是表示汽车被装载到船上进行运输的顺序。在这一点上，汽车没有任何所有者，我们真的只关心它们在哪个位置。然后，我想换掉汽车真的没有什么坏处，即节点引用的对象的内容。

Finally to the code. As I said above, I haven't been able to avoid the special-casing for adjacent nodes.

最后上代码。正如我上面所说，我无法避免相邻节点的特殊情况。

First, the definition of an auxiliary method:

一、辅助方法的定义：

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;
}

This method finds a node by its value. The integer returned is the zero-based position (call it its index if you like) of the node in the linked list. I found detecting adjacency through position, rather than pointer comparisons, more readable. The start of the list is root. The method sets n to point to the node containing the passed value. In pn, the method stores the predecessor of n.

此方法通过其值查找节点。返回的整数是链表中节点的从零开始的位置（如果你愿意，可以称之为它的索引）。我发现通过位置而不是指针比较来检测邻接更具可读性。列表的开头是 root。该方法将 n 设置为指向包含传递值的节点。在 pn 中，该方法存储 n 的前身。

The following is the actual swap:

以下是实际的交换：

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;
    }
}

I'm sorry that I have changed the signature of the OP's method a bit. I found it more convenient to pass in the values of the nodes to swap, as opposed to node pointers. If you pass in node pointers to the respective nodes only, you would have to do another traversal to find the predecessors with this solution, which felt a bit awkward to me. If we cannot distinguish nodes by these values, e.g. values are not unique, we will need pointers to the nodes, though.

很抱歉，我稍微更改了 OP 方法的签名。我发现传递节点的值进行交换更方便，而不是节点指针。如果只传入指向各自节点的节点指针，则需要再次遍历才能找到具有此解决方案的前辈，这让我感到有些尴尬。如果我们不能通过这些值区分节点，例如值不是唯一的，我们将需要指向节点的指针。

As with the explanation for find_node above, we first find the positions, nodes, and predecessors for the node values passed to swap_nodes through v1 and v2. The values for the first and second nodes are all swapped if the second node to swap appears before the first. It's not much code to do so, reduces special casing, and makes it a bit easier to visualize.

与上面对find_node的解释一样，我们首先找到通过v1和v2传递给swap_nodes的节点值的位置、节点和前驱。如果要交换的第二个节点出现在第一个之前，则第一个和第二个节点的值都将交换。这样做的代码并不多，减少了特殊的大小写，并使可视化更容易一些。

Now, we are left with just two more conditionals, neither of which seemed trivial to avoid. If the first node is at the head of the linked list, i.e. at position zero, the root needs to point to the second node. Otherwise, the first node's predecessor will point to the second node.

现在，我们只剩下两个条件，这两个条件似乎都不太容易避免。如果第一个节点位于链表的头部，即位置为零，则根需要指向第二个节点。否则，第一个节点的前驱将指向第二个节点。

The previous value of the first node's successor needs to be remembered, in case the nodes are not adjacent. Then, the first node's successor is set to the current successor of the second node. This is the only change that applies to all cases: the new successor of the first node being the old successor of the second node is the only certainty and helpful to start off with in order to remember the pointer operations and their sequence when implementing this swap.

需要记住第一个节点的后继节点的先前值，以防节点不相邻。然后，将第一个节点的后继设置为第二个节点的当前后继。这是唯一适用于所有情况的更改：第一个节点的新后继是第二个节点的旧后继是唯一确定的并且有助于在实现此交换时记住指针操作及其顺序.

Last, if the positions of the nodes differ by more than one, they are not adjacent. Then, the second node's new successor becomes the first node's old successor - saved away above - and the second node's predecessor now points to the first node. If they are adjacent, there are no nodes between the nodes to swap that need updating, so simply linking the second node to the first is all that is left to do.

最后，如果节点的位置相差超过 1，则它们不相邻。然后，第二个节点的新后继成为第一个节点的旧后继——保存在上面——第二个节点的前任现在指向第一个节点。如果它们相邻，则节点之间没有需要更新的要交换的节点，因此只需将第二个节点链接到第一个节点即可。