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

2024-05-20 • 问答

大家好，我正在尝试在两个双向链表之间完全交换两个节点（值和地址也是如此）。只有处于相同位置的节点可以交换，即位置 2 的节点只能被另一个链表中位置 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

代码不会交换之前的节点。

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

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

A19900919woaijisuanj 回答：如何在两个双向链表之间完全交换节点

大家都在问