反向打印鏈接列表

我正在處理反向打印鏈接列表而不銷燬的問題。我的具體問題是，反向打印鏈接列表

知道如果任何其他更好的想法，空間複雜度的提高，我現在的空間複雜度爲O(n)使用遞歸調用堆棧;
想知道提高算法時間複雜度的任何想法？

順便說一句：如果我當前的代碼有什麼問題，比如邏輯錯誤，請隨時提供建議。

class LinkedListNode: 
    def __init__(self, value, nextNode): 
     self.value = value 
     self.nextNode = nextNode 
    def print_reverse(self): 
     if not self.nextNode: 
      print self.value 
      return 
     else: 
      self.nextNode.print_reverse() 
      print self.value 
if __name__ == "__main__": 
    head = LinkedListNode('a', LinkedListNode('b', LinkedListNode('c', LinkedListNode('d', None)))) 
    head.print_reverse()

來源

2016-12-30 Lin Ma

的一個方向喜歡列表，這是你可以得到最好的複雜性。你可以創建一個雙鏈表（一個指向前一個節點的指針），並且你將擁有'O（1）'來處理複雜的內存。 – Matei

你print_reverse()可以簡化爲：

def print_reverse(self): 
    if self.nextNode: 
     self.nextNode.print_reverse() 
    print(self.value)

我看不出你如何能改善這一點，你需要一些描述堆棧，因爲這個名單不是雙向鏈表。但是你可以用你自己的堆棧，這將避免遞歸溢出的風險：

def print_reverse(self): 
    stack = [self] 
    nextNode = self.nextNode 
    while nextNode: 
     stack.append(nextNode) 
     nextNode = nextNode.nextNode 
    while stack: 
     print(stack.pop().value)

來源

2016-12-30 23:26:17 AChampion

如果您LinkedListNode的都不是一成不變的，你只關心鏈表的最終結構，你可以扭轉在一次迭代中鏈接列表，並打印元素，同時在另一次迭代中從末尾重新翻轉元素;這給你Ө(1)空間複雜度和Ө(n)時間複雜度。否則，如果你不允許在任何時候改變任何結構，我認爲Ө(n)空間是最好的，你可以得到。

這裏是一個Java實現：

class LinkedListNode { 
    int data; 
    LinkedListNode next; 
    LinkedListNode(int data) { this.data = data; } 
} 

class LinkedListReversePrintImplementation { 
    static void printReversely(LinkedListNode node) { 
     LinkedListNode currNode = node, 
         nextNode = node.next, 
         temp; 

     // Remove the link from first node 
     currNode.next = null; 

     // Reverse the other links 
     while (nextNode != null) { 
      temp = nextNode.next; 
      nextNode.next = currNode; 
      currNode = nextNode; 
      nextNode = temp; 
     } 

     // `currNode` now contains the last node 
     // Initialize the `nextNode` of the reversed linked list 
     nextNode = currNode.next; 

     // Remove the first link again 
     currNode.next = null; 

     // Print the last node 
     System.out.println(currNode.data); 

     // Print the other nodes while re-reversing it 
     while (nextNode != null) { 
      System.out.println(nextNode.data); 

      temp = nextNode.next; 
      nextNode.next = currNode; 
      currNode = nextNode; 
      nextNode = temp; 
     } 
    } 
}

來源

2016-12-30 23:28:10 smddzcy

混淆，這個'O（1）'空間複雜度如何？你不需要反向整理整個列表嗎？ – AChampion

@AChampion它接近'O（1）'，因爲你只需要存儲你正在交換的兩個值：'node1.next = None，node2.next = node1，node3.next = node2'。這絕對是不變的空間複雜性。 – Aaron3468

@ Aaron3468實際上它並不接近'O（1）'，它實際上是'O（1）'，因爲它是一個漸近分析。 – smddzcy

使用O（n）的空間來打印反向名單是不是很漂亮，尤其是如果的堆棧空間。

如果您不能修改該列表中，那麼你就可以做到這一點在O（日誌N）的空間和O（N日誌N）的時間是這樣的：

class LinkedListNode: 
    def __init__(self, value, nextNode): 
     self.value = value 
     self.nextNode = nextNode 

def count(list): 
    ret=0 
    while list: 
     ret+=1 
     list=list.nextNode 
    return ret 

def print_reverse(list,size=-1): 
    if size<0 and list: 
     size=count(list) 

    while size>1: 
     midpoint=size/2 
     tail=list 
     for _ in xrange(midpoint): 
      tail=tail.nextNode 
     print_reverse(tail,size-midpoint) 
     size=midpoint 
    if size>0: 
     print list.value 


head = tail = LinkedListNode(1,None) 
for n in range(2,29): 
    tail.nextNode=LinkedListNode(n,None) 
    tail=tail.nextNode 

print_reverse(head)

來源

2016-12-31 03:32:57

反向打印鏈接列表

回答

相關問題