在 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（新头）和return它作为新头。这并不优雅，您必须以 headNode = reversePair(headNode) 的形式调用该方法，但它应该可以工作。

在 Java 中反转一对链表

Reverse a linked list in a pair in Java

java

data-structures

linked-list

reverse