反向打印链接列表

我正在处理反向打印链接列表而不销毁的问题。我的具体问题是，反向打印链接列表

知道如果任何其他更好的想法，空间复杂度的提高，我现在的空间复杂度为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

反向打印链接列表

回答

相关问题