时间戳

首页 > 解决方案 > 如何在两个双向链表之间完全交换节点

c++ - 如何在两个双向链表之间完全交换节点

问题描述

大家好，我试图在两个双向链表之间完全交换两个节点（值和地址也是）。只有处于相同位置的节点才能相互交换，即位置2 的节点只能被另一个LinkedList 中位置2 的节点交换。考虑以下 2 个 LinkedList 的示例：

815 102 162 524 
622 101 830 754

假设我们要交换第三个元素，即 162 和 830。交换 LinkedLists 后变为：

815 102 830 524 
622 101 162 754

我已经尝试了以下代码，但它不会交换以前的元素。

void swapNodes(Node* firstListNode, Node* secondListNode)
{
    Node* FirstNodeNext = firstListNode->next;
    Node* FirstNodePrev = firstListNode->previous;
    Node* SecondNodeNext = secondListNode->next;
    Node* SecondNodePrev = secondListNode->previous;
    
    //if the nodes are heads
    if (firstListNode->previous == NULL && secondListNode->previous == NULL)
    {   
        firstListNode->next = SecondNodeNext;
        secondListNode->next = FirstNodeNext;
    }
    // if the nodes are tails
    else if(firstListNode->next == NULL && secondListNode->next == NULL)
    {
        firstListNode->previous = SecondNodePrev;
        secondListNode->previous = FirstNodePrev;
    }
    else
    {
        firstListNode->next = SecondNodeNext;
        firstListNode->previous = SecondNodePrev;

        secondListNode->next = FirstNodeNext;
        secondListNode->previous = FirstNodePrev;
     }
}

我怎样才能完成这项任务？

else if 不交换前面的元素，例如，如果我们将值 524 和 754 传递给函数，它应该是尾部并执行 else if 语句，因为它没有下一个节点。

交换后应该是：

815 102 162 754
622 101 830 524

该代码不会交换先前的节点。

标签： c++data-structureslinked-listdoubly-linked-list

解决方案

我认为您正在丢失在其他链表中交换的引用，下面是 java 中相同的工作代码片段。请注意，我在这里假设两个链表的长度相同。

public class Application {

    static class Node{
        private int value;
        private Node prev;
        private Node next;

        public Node(int value){
            this.value = value;
        }

        public void print(){
            for(Node node=this; node!=null; node = node.next){
                System.out.print(node.value + "->");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        Node head1 = new Node(815);
        addNodeAtLast(head1, 102);
        addNodeAtLast(head1, 162);
        addNodeAtLast(head1, 524);
        head1.print();

        Node head2 = new Node(622);
        addNodeAtLast(head2, 101);
        addNodeAtLast(head2, 830);
        addNodeAtLast(head2, 754);
        head2.print();

        swapAtIndex(head1, head2, 3);
        head1.print();
        head2.print();
    }

    private static void swapAtIndex(Node head1, Node head2, int index){
        System.out.println("Swaping node at index : "+index);
        if(index == 0){
            Node tmp = head1.next;
            head1.next= head2.next;
            head2.next = tmp;
            return;
        }
        Node linkedList1Ref = head1,  linkedList2Ref = head2;
        for(int i=0; i!=index; ++i, linkedList1Ref = linkedList1Ref.next, linkedList2Ref=linkedList2Ref.next);

        Node temp2Prev = linkedList2Ref.prev;
        Node temp2Nxt = linkedList2Ref.next;

        linkedList1Ref.prev.next = linkedList2Ref; // LinkedList 1 swap
        linkedList2Ref.prev = linkedList1Ref.prev; // LinkedList 1 swap
        if(linkedList2Ref.next != null && linkedList1Ref.next != null) {
            linkedList2Ref.next = linkedList1Ref.next; // LinkedList 1 swap
            linkedList1Ref.next.prev = linkedList2Ref; // LinkedList 1 swap
        }

        temp2Prev.next = linkedList1Ref;
        linkedList1Ref.prev = temp2Prev;
        if(linkedList1Ref.next != null && temp2Nxt != null) {
            linkedList1Ref.next = temp2Nxt;
            temp2Nxt.prev = linkedList1Ref;
        }
    }

    private static void addNodeAtLast(Node head, int value){
        Node temp = new Node(value);
        Node prev = null;
        for(prev=head; prev.next != null; prev=prev.next);
        temp.prev = prev;
        prev.next = temp;
    }
}

推荐阅读