反向打印linkedlist

Question

我正在研究一个不销毁的反向打印链表的问题。我的具体问题是

1. 不知道还有没有更好的想法，空间复杂度的提高，我目前的空间复杂度是O(n)使用递归调用堆栈
2. 想知道有什么方法可以提高算法的时间复杂度吗？你知道吗

顺便说一句：如果我现在的代码有什么问题，比如逻辑错误，请随时提出建议。你知道吗

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()

Answer 1

如果您的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;
        }
    }
}

Answer 2

使用O（n）空格反向打印列表不是很好，特别是如果这是堆栈空间。你知道吗

如果不能修改列表，则可以在O（logn）空间和O（nlogn）时间中进行修改，如下所示：

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)

Answer 3

您的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)