反转线性链表

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

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;.... } } 

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

我开始开发反转function，但我不确定。 有任何想法吗？

更新：可能存在递归方式，因为线性链表是递归数据结构。

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

Answer 1

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

1. 空列表的反向是空列表。
2. 单身人士名单的反面就是其本身。
3. 节点N的列表的后面跟随列表L是列表L的后面，后面是节点N.

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

 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）中使用它。 假设您有一个如下所示的链接列表：

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

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

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

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

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

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

 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所指出的，这会将调用堆栈用于其存储空间，从而存在堆栈溢出的风险。 如果你想使用显式堆栈，你可以这样做：

 void reverseList(Node node) { /* Make a stack of the reverse of the nodes. */ Stack s = new Stack(); 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; } } 

我相信这同样颠倒了链表元素。

Answer 2

我有时在采访中问这个问题……

我不建议使用递归解决方案， 或使用堆栈来解决此问题。 为这样的任务分配O（n）内存是没有意义的。

这是一个简单的O（1）解决方案（我现在没有运行它，所以如果它需要一些修正我道歉）。

 Node reverse (Node current) { Node prev = null; while (current != null) { Node nextNode = current.next; current.next = prev; prev = current; current = nextNode; } return prev; } 

BTW： lappend方法有效吗？ 看起来它总是抛出NullReferenceException 。

Answer 3

我会将当前列表视为堆栈 （这是我的伪代码）：

 Node x = copyOf(list.head); x.link = null; foreach(node in list){ Node temp = copyOf(list.head); temp.link = x; x = temp; } 

最后， x将成为颠倒列表的头部。

Answer 4

我更熟悉的是C，但还是让我试试。 （我只是不确定它是否在Java中运行，但它应该）

 node n = (well first one) node prev = NULL; node t; while(n != NULL) { t = n.next; n.next = prev; prev = n; n = t; } 

Answer 5

反转单链表是一个经典问题。 这里也回答了（并且得到了很好的回答），它不需要递归也不需要额外的内存，除了寄存器（或2）以供参考保存。 然而对于OP，我想这是一个学校项目/家庭作业和一些建议，如果你曾经使用单链表进行一些真正的数据存储，也可以考虑使用尾节点。 （截至目前，单个链表几乎已经绝迹，但我想到了HashMap存储桶）。 除非你必须在’add’期间检查所有节点的某些条件，否则尾部是一个很大的改进。 下面是一些代码，它们具有反向方法和尾节点。

 package t1; public class SList { Node head = new Node(); Node tail = head; private static class Node{ Node link; int data; } void add(int i){ Node n = new Node(); n.data = i; tail = tail.link =n; } void reverse(){ tail = head; head = reverse(head); tail.link = null;//former head still links back, so clear it } private static Node reverse(Node head){ for (Node n=head.link, link; n!=null; n=link){//essentially replace head w/ the next and relink link = n.link; n.link = head; head = n; } return head; } void print(){ for (Node n=head; n!=null;n=n.link){ System.out.println(n.data); } } public static void main(String[] args) { SList l = new SList(); l.add(1);l.add(2);l.add(3);l.add(4); l.print(); System.out.println("=="); l.reverse(); l.print(); } } 

Answer 6

我想知道这样的事情（我没有测试过，所以）：

 invert(){ m(firstNode, null); } m(Node v, Node bef){ if(v.link != null) m(v.link,v); else v.link=bef; } 

Answer 7

没有太多测试，

 Node head = this; Node middle = null; Node trail = null; while (head != null) { trail = middle; middle = head; head = head.link; middle.link = trail; } head = middle; return head; 

Answer 8

 public ListNode Reverse(ListNode list) { if (list == null) return null; if (list.next == null) return list; ListNode secondElem = list.next; ListNode reverseRest = Reverse(secondElem); secondElem.Next = list; return reverseRest; } 

希望这可以帮助。