反转线性链表 [英] Invert linear linked list

问题描述

线性链表是一组节点。这就是节点的定义方式（为了方便起见，我们不区分节点和列表）：

a linear linked list is a set of nodes. This is how a node is defined (to keep it easy we do not distinguish between node an list):

class Node{
    Object data;
    Node link;

    public Node(Object pData, Node pLink){
        this.data = pData;
        this.link = pLink;
    }

    public String toString(){
        if(this.link != null){
            return this.data.toString() + this.link.toString();
        }else{
            return this.data.toString() ;
        }
    }

    public void inc(){
        this.data = new Integer((Integer)this.data + 1);
    }

    public void lappend(Node list){
        Node child = this.link;
        while(child != null){
            child = child.link;
        }
        child.link = list;
    }

    public Node copy(){
        if(this.link != null){
            return new Node(new Integer((Integer)this.data), this.link.copy());
        }else{
            return new Node(new Integer((Integer)this.data), null);
        }
    }

    public Node invert(){
        Node child = this.link;
        while(child != null){
            child = child.link;
        }
        child.link = this;....
    }
}

我可以制作清单的深层副本。现在我想反转列表，以便第一个节点是最后一个节点，最后一个节点是第一个节点。倒置列表必须是深层复制。

I am able to make a deep copy of the list. Now I want to invert the list so that the first node is the last and the last the first. The inverted list has to be a deep copy.

我开始开发反转功能，但我不确定。任何想法？

I started developing the invert function but I am not sure. Any Ideas?

更新：可能有一种递归方式，因为线性链表是一个递归数据结构。

Update: Maybe there is a recursive way since the linear linked list is a recursive data structure.

我会接受第一个元素，遍历列表直到我到达一个没有子节点的节点并附加第一个元素，我会重复第二个，第三个....

I would take the first element, iterate through the list until I get to a node that has no child and append the first element, I would repeat this for the second, third....

推荐答案

基于以下观察，这个问题有一个很好的递归解决方案：

There's a great recursive solution to this problem based on the following observations:

1. 空列表的反面是空列表。


2. 单例列表的反向本身。


3. 列表的反向节点N后跟列表L的后面是列表L的反向，后跟节点N.

因此，您可以实现使用伪代码沿这些行的反向函数：

You can therefore implement the reverse function using pseudocode along these lines:

void reverseList(Node node) {
    if (node == null) return;      // Reverse of empty list is itself.
    if (node.next == null) return; // Reverse of singleton list is itself.

    reverseList(node.next); // Reverse the rest of the list
    appendNodeToList(node, node.next); // Append the new value.
}

此算法的简单实现在O（n ² ），因为每次反转都需要一个追加，这需要对列表的其余部分进行O（n）扫描。但是，您实际上可以使用聪明的观察在O（n）中使用它。假设您有一个如下所示的链接列表：

A naive implementation of this algorithm runs in O(n²), since each reversal requires an append, which requires an O(n) scan over the rest of the list. However, you can actually get this working in O(n) using a clever observation. Suppose that you have a linked list that looks like this:

n1 --> n2 --> [rest of the list]

如果从n2开始反转列表，那么你最终会得到这个设置：

If you reverse the list beginning at n2, then you end up with this setup:

n1       [reverse of rest of the list] --> n2
 |                                          ^
 +------------------------------------------+

因此，您可以通过设置将n1附加到列表其余部分的反面n1.next.next = n1 ，更改 n2 ，反向列表的新结尾，指向n1：

So you can append n1 to the reverse of the rest of the list by setting n1.next.next = n1, which changes n2, the new end of the reverse list, to point at n1:

[reverse of the rest of the list] --> n2 --> n1

你是金色的！再次更多伪代码：

And you're golden! Again more pseudocode:

void reverseList(Node node) {
    if (node == null) return;      // Reverse of empty list is itself.
    if (node.next == null) return; // Reverse of singleton list is itself.

    reverseList(node.next); // Reverse the rest of the list
    node.next.next = node; // Append the new value.
}

编辑：正如Ran指出的那样，它使用调用堆栈作为其存储空间因此存在堆栈溢出的风险。如果你想使用显式堆栈，你可以这样做：

As Ran pointed out, this uses the call stack for its storage space and thus risks a stack overflow. If you want to use an explicit stack instead, you can do so like this:

void reverseList(Node node) {
    /* Make a stack of the reverse of the nodes. */
    Stack<Node> s = new Stack<Node>();
    for (Node curr = node; node != null; node = node.next)
        s.push(curr);

    /* Start unwinding it. */
    Node curr = null;
    while (!s.empty()) {
        Node top = s.pop();

        /* If there is no node in the list yet, set it to the current node. */
        if (curr == null)
            curr = top;
        /* Otherwise, have the current node point to this next node. */
        else
            curr.next = top;

        /* Update the current pointer to be this new node. */
        curr = top;
    }
}

我认为这类似地反转了链表元素。

I believe that this similarly inverts the linked list elements.

这篇关于反转线性链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！