链表反转的图示指南
本文最初发表于https://algodaily.com，我在该网站上维护一个技术面试课程，并为有抱负的开发者撰写思考性文章。
你收到一串linked list数字，但顺序与你需要的相反。这种情况已经发生多次，所以你决定编写一个算法来反转收到的列表。你收到的列表如下：
// 17 -> 2 -> 21 -> 6 -> 42 -> 10
编写一个算法，reverseList该方法接受一个head节点作为参数，并反转链表。该算法应能够反转任意长度的链表。
您可以将此示例linked list用于测试目的。您的方法将按如下方式调用：
class LinkedListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
l1 = new LinkedListNode(1);
l1.next = new LinkedListNode(2);
reverseList(l1);
看起来很简单，对吧？要反转整个链表，只需反转每个指针。如果1指针指向 A 2，则将其翻转，2使其指向1B。
// 17 -> 2 -> 21 -> 6 -> 42 -> 10
// becomes
// 17 <- 2 <- 21 <- 6 <- 42 <- 10
实际的逆向推导方法其实相当简单直接，但要注意的是，它需要一些时间来理清思路。很容易迷失方向，所以一定要画很多图表。
由于这是一个可以分解为子问题（反转整个链表）的问题（反转两个节点之间的指针），因此这似乎是一个很好的使用递归的机会。
实现实际逆操作的方法有很多种，我们将介绍迭代法和递归法，但总体方法如下：
- 首先创建 3 个指针：
newHead，head和nextNode。newHead并nextNode初始化为null。head开始时指向链表的头部。
- 重复（或递归地）以下步骤，直到
head达到 n=1null。这意味着已到达列表末尾：
class LinkedListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
l1 = new LinkedListNode(1);
l2 = new LinkedListNode(2);
l1.next = l2;
// we start at head
let head = l1;
let newHead = null;
while (head != null) {
// store the node to the right to reuse later
let nextNode = head.next;
// set the current node's next to point backwards
head.next = newHead;
// store the current node, to be used as the new next later
newHead = head;
// the previously right-side node is now processed
head = nextNode;
}
console.log(l2);
这一系列事件很难用图像来呈现，所以我们用评论来形象化。面试时，尽量不要一直想着这件事。
在与面试官交谈的同时保持冷静和理清思路，会尤其困难。要充分利用白板，不仅用来记录内容，还要用来思考可能的步骤。
让我们一步一步来，然后再看一下运行的代码。我们先来反转一个非常简单的列表，比如 `[] 8 -> 4`。第一行是 `[]` let nextNode = head.next;，它会存储右边的节点。
nextNode = 4
// 8 -> 4
然后我们将执行head.next = newHead;，这将使当前节点的next指向向后。
nextNode = 4
// <- 8, 4
现在newHead = head;将存储当前节点，以便稍后用作新的下一个节点。
newHead = 8
nextNode = 4
// <- 8, 4
最后，之前位于右侧的节点现在被处理：
newHead = 8
nextNode = 4
// <- 8, 4
^
current node
现在我们用同样的步骤处理下一个节点，nextNode = head.next;并将右侧的节点存储起来。
newHead = 8
nextNode = null
// <- 8, 4
^
current node
再次，将当前节点的next指针指向后方head.next = newHead;。记住，这newHead是8！这就是我们进行切换的地方：
newHead = 8
nextNode = null
// <- 8 <- 4
^
current node
现在让我们看看如何用代码实现这一切，并附上大量的注释以供参考！
class LinkedListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
l1 = new LinkedListNode(8);
l2 = new LinkedListNode(4);
l1.next = l2;
// start at head, 8
let head = l1;
// example: 8 -> 4
let newHead = null;
while (head) {
/* FIRST PASS */
// store the node to the right
let nextNode = head.next;
// nextNode = 4, still 8 -> 4
// set the current node's next to point backwards
head.next = newHead;
// 8 -> null
// store the current node, to be used as the new next later
newHead = head;
// newHead = 8
// the previously right-side node is now processed
head = nextNode;
// head = 4
/* SECOND PASS */
// store the node to the right
nextNode = head.next;
// nextNode = null
// set the current node's next to point backwards
head.next = newHead;
// 4 -> 8
// store the current node as the previous one
newHead = head;
// the previously right-side node is now processed
head = nextNode;
}
console.log(l2);
这样说都明白了吗？一定要反复尝试几次这种迭代方法。
以下是递归实现方法。这种方法乍一看可能有点棘手，但要知道，大部分的神奇之处都发生在最后。
function reverseList(head) {
if (!head || !head.next) {
return head;
}
let rest = reverseList(head.next);
head.next.next = head;
delete head.next;
return rest;
}
让我们再举一个简单的例子，8 -> 4看看它let rest = reverseList(head.next);如何运作4和调用reverseList。
reverseList这样做4会让我们触及终止条款，因为没有.next：
if (!head || !head.next) {
return head;
}
我们向上追溯堆栈，回到8处理数据时的状态。rest现在它指向的就是之前的状态4。现在请注意发生了什么：
// remember, head is 8 - it is being processed
// head.next is 4
head.next.next = head;
// head.next.next was null since 4 wasn't pointing to anything
// but now head.next (4) points to 8
我们返回4——它指向8。我们可以简单地将其推广到更长的链表！请注意，递归方法需要更多空间，因为我们需要维护调用栈。