交换链表中的链接，结果不正确

Question

 public void question1(int key1,int key2){
    //swapping keys by changing links not data:
    Node temp = Head;
    Node tempStr1 = null;
    Node nextStr1=null,NextStr2=null;
    Node tempstr2 = null;
    while(temp.Next!=null){
        if(temp.Next.data==key1){
            nextStr1=temp.Next.Next;
            tempStr1 = temp.Next;
        }
        if(temp.Next.data==key2){
            NextStr2 = temp.Next.Next;
            tempstr2 = temp.Next;//storing in temp var
        }
        temp=temp.Next;//update
    }
    while(temp.Next!=null){
        if(temp.Next.data==key1){
            temp.Next = tempstr2;
            tempstr2.Next = nextStr1;
        }
        if(temp.Next.data==key2){
            temp.Next = tempStr1;//swap
            tempStr1.Next = NextStr2;
        }
        temp=temp.Next;//update
    }

}
    }
public static void main(String args[]){
        LinkedList ll = new LinkedList();
        ll.addFirst(1);
        ll.addFirst(2);
        ll.addFirst(3);
        ll.addFirst(4);
        ll.addFirst(5);
        ll.addFirst(6);
        ll.Print();
        ll.question1(3, 2 );
       ll.Print();

我不明白为什么这不起作用。 目标是通过更改链接来交换两个节点。

预期结果：

6 5 4 2 3 1

真实结果：

6 5 4 3 2 1

此代码适用于这个问题：

交换链表中的节点

我们有一个链表和其中两个键，交换两个给定键的节点。应通过更改链接来交换节点。当数据包含许多字段时，在许多情况下交换节点数据可能会很昂贵。可以假设链表中的所有键都是不同的。

Answer 1

有几个问题：

• 第二个循环永远不会迭代，因为当

  temp.Next

  为

  null

  时，第一个循环将结束，并且由于第二个循环只有在不是情况下才会迭代，所以它是无用的。这实际上意味着永远不会有交换。

• 即使您在第二个循环开始之前将

  temp

  重置为

  null

  ，遗憾的是您需要再次迭代整个列表，只是为了再次找到相同的两个节点。

• 如果在第二个循环中第一个条件为真，则第一个

  if

   块将使 

  temp.Next

   引用带有 key2 的节点，但这意味着第二个 

  if

   条件现在也为真，并且更改将再次恢复。

• 没有规定必须交换

  head节点。

• 不区分两个

  连续节点需要交换（涉及更新3个引用）和交换节点不是彼此邻居的情况（涉及更新4个引用）。

我建议你只有一个循环，当你找到两个位置后，立即进行交换。

此外，为了将头作为交换的潜在候选者，我建议暂时在列表前面添加一个虚拟节点，以便

while

 循环可以提前一步开始，并在头节点中检测到所需的密钥。交换后，应再次删除该虚拟节点。这样，最终的 

Head

 节点实际上可能与最初的情况不同。

这是建议的代码：

    public void question1(int key1, int key2) {
        // Swapping keys by changing links not data:
        addFirst(0); // Prepend list with some dummy value
        Node temp = null; // Used for swapping
        Node before1 = null; // Node that precedes the first match
        Node before2 = Head; // Node that eventually precedes the second match
        
        while (before2.Next != null) {
            if (before2.Next.data == key1 || before2.Next.data == key2) {
                if (before1 == null) { // First match
                    before1 = before2;  // Save that match
                } else { // Second match
                    if (before1.Next == before2) { // Special case
                        before1.Next = before2.Next;
                        before2.Next = before2.Next.Next;
                        before1.Next.Next = before2;
                    } else {
                        temp = before1.Next.Next;
                        before1.Next.Next = before2.Next.Next;
                        before2.Next.Next = temp;
            
                        temp = before1.Next;
                        before1.Next = before2.Next;
                        before2.Next = temp;
                    }
                    break; // All done
                }
            }
            before2 = before2.Next;
        }
        // Remove the dummy Node
        Head = Head.Next;
    }