在单个链表上交换节点

2022-01-01 00:00:00 swap linked-list c++

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

I am trying to make a swapNode function 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.

这是我目前所写的:

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

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

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;

这个似乎也不起作用，我遇到了段错误.

This one doesn't seem to work either, I get a seg fault.

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

推荐答案

说我们有:

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

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

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

因此，要交换 Node2 和 Node3，您实际上必须将 Node1->next 与 Node2->next 和 Node2- 交换>next 和 Node3->next.即使它们彼此相邻(或者即使它们是同一个节点)，这也会起作用.例如:

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

交换 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

交换！

正如评论部分中提到的，如果用任何东西交换 Node1，你必须为链表设置一个新的头.

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

针对问题的

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

Your code for swapping almost right. 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 next values 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:

//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 变量 - 这可能是某处的分配或删除错误.你从哪里得到段错误?

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?

相关文章