迭代地反转单链表 [英] Reversing a singly linked list iteratively

问题描述

必须是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;
        }
    }

这篇关于迭代地反转单链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！