反转链接列表

Question

我正在用Java编写一个简单的递归代码来反转链表。奇怪的是，它返回相同的节点。

Node reverse(Node ptr) {
    if (ptr.link == null)
        return ptr;
    Node second = ptr.link;
    ptr.link = null;
    Node rest = reverse(second);
    rest.link = ptr;
    return rest;
}

为什么不起作用？

Answer 1

您当前的方法不起作用，递归调用返回的rest值没有指向列表中的最后一个元素(应该是节点的插入点(，而是指向结果的第一个元素。换句话说，这一行没有正确构建输出：

rest.link = ptr;

为了成功地反转列表，一种策略是使用累加器参数，这样我们就可以在递归展开时在列表的开头插入-请记住，递归开始以与列表中元素相反的顺序"返回"。试试这个，这是一个尾部递归解决方案：

Node reverse(Node ptr, Node acc) {
    if (ptr == null)
        return acc;
    Node second = ptr.link;
    ptr.link = acc;
    return reverse(second, ptr);
}

这样调用上面的方法：

Node reversedList = reverse(list, null);

请注意，输入list将被修改，并且在方法返回后将不相同，任何引用list的变量都将受到影响。如果这是一个问题，您应该在将list的副本传递给reverse()之前创建它。

Answer 2

Oscar认为递归调用的返回值不指向最后一个元素是正确的。

还有一种算法不使用累加器参数：

function reverse(node) {
  if (node.next == null)
    return node;
  var tail = reverse(node.next);
  node.next.next = node;
  node.next = null;
  return tail;
}

Answer 3

Node reverseNode(Node node){
Node head = null;
While(node.next != null){
    Node n = new Node(node.data);
    n.next = head;
    head = n;
    node = node.next;
}
return head;}

您知道不必编写递归函数