在单个链表上交换节点

Question

我正在尝试创建一个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;

编辑2:这个似乎也没有用,我得到一个段错误.

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

交换!

在评论部分中注意到,如果将Node1与任何内容交换,则必须为链表设置新头.

针对问题的编辑:

你的交换代码几乎是正确的.但是,您需要将firstPrev与secPrev交换.在我的例子中就是这样,我们交换了一个节点的next值两次,因为它们彼此相邻.但从逻辑上讲,我们想要交换next前两个的s,然后交换next实际节点的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;

如果您遇到段错误,请检查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;
}

如果这是不允许的,那么你想在 - > next而不是 - > value组件上进行类似样式的交换.然后在firstPrev-> next和secondPrev-> next组件上进行另一次交换.注意第一或第二= =头的特殊情况.