在 Java 中反转一对链表
Reverse a linked list in a pair in Java
我正在 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
,不知道这里有什么逻辑漏洞
你能解释一下我的代码中有什么问题和解决方案吗?
您的代码中有两个问题。第一个是你传递给方法的节点在方法外没有改变,它仍然指向 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 学习数据结构。
我有一个链表:
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
,不知道这里有什么逻辑漏洞
你能解释一下我的代码中有什么问题和解决方案吗?
您的代码中有两个问题。第一个是你传递给方法的节点在方法外没有改变,它仍然指向 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)
的形式调用该方法,但它应该可以工作。