本文介绍了迭代地反转单链表的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
必须是O(n)和就地(空间复杂度为1)。下面的代码确实有效,但有更简单或更好的方法吗?
Has to be O(n) and in-place (space complexity of 1). The code below does work, but is there a simpler or better way?
public void invert() {
if (this.getHead() == null)
return;
if (this.getHead().getNext() == null)
return;
//this method should reverse the order of this linked list in O(n) time
Node<E> prevNode = this.getHead().getNext();
Node<E> nextNode = this.getHead().getNext().getNext();
prevNode.setNext(this.getHead());
this.getHead().setNext(nextNode);
nextNode = nextNode.getNext();
while (this.getHead().getNext() != null)
{
this.getHead().getNext().setNext(prevNode);
prevNode = this.getHead().getNext();
this.getHead().setNext(nextNode);
if (nextNode != null)
nextNode = nextNode.getNext();
}
this.head = prevNode;
}
推荐答案
编辑删除额外比较每次迭代:
Edited to remove the extra comparison per iteration:
public void invert() {
Node<E> prev = null, next = null;;
if (head == null) return;
while (true) {
next = head.getNext();
head.setNext(prev);
prev = head;
if (next == null) return;
head = next;
}
}
这篇关于迭代地反转单链表的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!