反向链表的不同实现

Question

我在php中发现了几个反向链表实现，其中大多数都是相同的，但有一些小的区别，比如：

public function reverse() {
    if ( $this->_firstNode !== NULL ) {
        if ( $this->_firstNode->next !== NULL ) {
            $reversed = $temp = NULL;
            $current = $this->_firstNode;
            while ( $current !== NULL ) {
                $temp = $current->next;
                $current->next = $reversed;
                $reversed = $current;
                $current = $temp;
            }
            $this->_firstNode = $reversed;
        }
    }
}

但我认为可以改成这样：

public function reverse() {
    while ( $this->_firstNode->next !== NULL ) {
        $oldFirstNode = $this->_firstNode;
        $this->_firstNode = $oldFirstNode->next;
        $oldFirstNode->next = NULL;
        $this->_firstNode->next = $oldFirstNode;    
    }
}

我说得对吗？

Answer 1

您的代码不起作用，原因有两个：

1. 您不测试空列表。该方法不考虑$this->_firstNode是NULL的情况
2. 如果列表仅包含一个元素，则该方法不起作用
3. 如果列表包含两个或多个元素，则该方法只反转列表的前两个元素，然后陷入无休止的循环。这是因为在的正文的最后一行中，您用$oldFirstNode的值更新$this->_firstNode->next，在下一次迭代中，您检查$this->_firstNode->next !== NULL，它与NULL不同，因为它是$oldFirstNode的值，并且函数继续在这两个节点上循环

对于像这样的算法，最好的方法是用纸和铅笔绘制列表中的元素和指向它们的变量，并按照算法一步一步地更新它们。

最后要注意的是，如果一个算法总是用于某个基本任务，那么很难找到一个新的、更高效的算法。