这是递归反转链接列表的正确方法吗?

Question

我的反向链表函数似乎有问题，但即使在网上寻找解决方案，我也无法理解为什么我的方法在三个节点的试运行中失败:(在其他解决方案中，带星标的部分通常写为"head.next.next = head"。我的"n.next = head"行不是在做同样的事情吗？

在调用该方法之前，其他一些解决方案也有一行：

Node secondElem = head.next;
head.next = NULL;

我也不明白为什么需要这个:(

我想出了这个解决方案，似乎无法从这里继续：

Node reverseLL(Node head){
if (head == NULL || head.next == NULL) return head;
Node n = reverseLL(head.next);
n.next = head; //**
head.next = NULL 
return n;
}

有人可以向我解释一下吗？

Answer 1

当你递

归地反转链表时，你需要将前一个头附加到最后。这是列表其余部分反转的结果并没有真正帮助的地方 - 事实上，您最终只想返回它。

但有一件事需要注意：第二个元素将成为列表的反向其余元素的最后一个元素。在颠倒其余部分后，head.next仍将保留对它的引用。

例

原始列表

head = 1 -> 2 -> 3 -> NULL

从递归调用返回的反向子列表(head仍将为 1，head.next仍将指向 2(

3 -> 2 -> NULL

您可以使用它来将头附加到反转其余部分的递归调用之后的末尾：

Node reverseLL(Node head) {
  if (head == NULL || head.next == NULL) return head;
  Node n = reverseLL(head.next);
  head.next.next = head;  
  head.next = NULL;
  return n;
}