關於遞歸實現反轉單向鏈表的問題

Question

如果我創建了鏈接列表，其中插入順序是5,4,3。我使用頭部參考，因此鏈接列表被存儲爲3->4->5->null。

當我想反轉鏈接列表==原來的插入順序，所以它會是
5->4->3->null。現在，如果這是我的新列表的外觀，我的頭引用哪個節點應該引用這樣的新元素，我添加到列表中仍然會有O（1）插入時間？

Answer 1

我認爲，根據定義，頭總是指向列表的第一個元素。

如果要插入到O（1）中鏈表的末尾，則保留兩個引用，一個引用第一個元素，一個引用最後一個元素。然後通過跟隨最後一個元素的最後一個引用，在最後一個元素之外添加新元素，將最後一個引用更新爲指向新的最後一個元素來完成添加。

插入到空列表成爲一種特殊情況，因爲您必須設置第一個引用和最後一個引用，而不僅僅是最後一個引用。同樣，從一個元素的列表中刪除。

Answer 2

如果你想要一個單獨鏈接列表的後面，你應該保留對最後一個元素的引用。當你要插入一個新的元素，將創建爲頭新元素的新鏈接對象，該元素的尾部之後你將它插入尾部，新的鏈接對象爲元素的新尾巴將其插入之後。這需要三個指針移動並且因此持續時間。

Answer 3

認爲它是這樣的：

由HEAD -> [the rest of the list]列表的反向恰恰是：reverse([the rest of the list]) -> HEAD。

您的基本情況是如果列表包含單個元素。這樣的清單恰恰相反。

下面是一個例子（使用可執行的僞代碼，又名的Python）：

class Node(object): 

    def __init__(self, data, next_=None): 
     self._data = data 
     self._next = next_ 

    def __str__(self): 
     return '[%s] -> %s' % (self._data, 
       self._next or 'nil') 


def reverse(node): 
    # base case 
    if node._next is None: 
     return node 

    # recursive 
    head = Node(node._data)  # make a [HEAD] -> nil 
    tail_reverse = reverse(node._next) 

    # traverse tail_reverse 
    current = tail_reverse 
    while current._next is not None: 
     current = current._next 
    current._next = head 

    return tail_reverse 


if __name__ == '__main__': 
    head = Node(0, 
      Node(1, 
       Node(2, 
        Node(3)))) 
    print head 
    print reverse(head) 

注意，這不是在O（1）由於缺少在最後元件的參考（僅HEAD）的。

Answer 4

對於任何鏈表有一個O（1）的插入時間，則必須插入到列表中或完全不考慮任何順序一些其他任意位置的前面。作爲一個單向鏈表意味着你不能指向最後一個元素列表，因爲該列表，直到最後一個元素將無法訪問。修復程序到這可能是因爲香遣散曾表示在您保持兩個指針，一個頭部和尾部。您可以使用頭部訪問元素和尾部，以將元素任意添加到列表中。