java - 在 Java 中反转一对链表

Question

我正在学习 Java 数据结构。

我有一个链接列表:

1 -> 2 -> 3 -> 4 -> 5

我想反转链表，但是是成对的。

2 -> 1 -> 4 -> 3 -> 5

我写了一个代码，但它不起作用

private void reversePair(Node headNode) {
    Node tempNode1 = null;
    Node tempNode2 = null;
    Node currentNode = headNode;

    while(currentNode != null && currentNode.getNext() != null) {
        tempNode1 = currentNode.getNext();
        tempNode2 = tempNode1.getNext();

        tempNode1.setNext(currentNode);
        currentNode.setNext(tempNode2);

        currentNode = currentNode.getNext();
    }
}

变成了1 -> 3 -> 5，我不知道这里有什么逻辑漏洞。

您能解释一下我的代码中存在什么问题以及解决方案吗？

Answer 1

您的代码中有两个问题。第一个是你传递给方法的节点在方法之外没有改变，它仍然指向1!第二个问题是在 while 循环内部......你做了类似的事情

temp1->2, temp2->3 之后是 2->1 和 1->3 在你获得的时候结束

2->1->3->4->....那没问题但现在:

1) 正如我所说的 headNode，在方法之外，指向 1，所以它将列表视为1->3->4->...

2) 接下来的 while 迭代交换 3 和 4 (4->3,3->5)，但 1 仍然指向 3，它没有改变!因此方法外部的 headNode 将列表视为 1->3->5->...

解决第二个问题应该很容易。第一个比较困难，我建议保存2个(新头)并将其作为新头返回。这并不优雅，您必须将该方法调用为 headNode = reversePair(headNode) 但它应该可以工作。