使用图解的方式来解决链表的算法问题

这周在刷链表的算法时，发现对于这类问题用图解的方式来解决十分简单。通常我们的草图画完了，代码也就随之写出来了，不用绞尽脑汁去想 p.next = new Node(); p = p.next 这么绕的代码。

下面我们通过两道算法来说明一下图解的方式有多便利。

数组转链表

首先是一个比较简单的数组转链表的问题。代码如下：

//声明一个单链表结点class ListNode {  constructor(val) {    this.val = val;    this.next = null;  }}/** * 数组转链表 * @param {Array} arr  * @return {ListNode}  */export function array2List(arr) {  if (arr.length === 0) {    return null;  }  const head = new ListNode(null);  let i = 0, curr = head;  for (i; i < arr.length; i++) {    curr.next = new ListNode(arr[i]);    curr = curr.next;  }  return head.next;}

代码比较简单，但发现很多小伙伴对于下面这几行代码直接去看的话不是很明白：

curr = headcurr.next = new ListNode(arr[i]);curr = curr.next;

我们自己实现的 ListNode 在 JavaScript 中实际上是一个引用类型，通过画出堆栈图，其实就很容易明白了。关于 JavaScript 的值类型与引用类型这里就不再赘述了。

下面我们来逐一分析这个图解。

首先，STEP 0 做的事情就是下面这两句代码：

const head = new ListNode(null);let curr = head;

由于 ListNode 是引用类型，它存放在堆内存中。head 和 curr 保存的是在栈内存中的一个引用，实际上指向的都是堆内存中的 ListNode。

STEP 1 就是第一次循环做的事情。循环体里就两句代码，也是最核心的部分：

curr.next = new ListNode(arr[i]);curr = curr.next;

我们通过图解可以看到，new ListNode(arr[i]) 在堆内存中又生成了一个新的 ListNode，我们用 ListNode1 来表示。堆内存中原来的 ListNode 的 next 属性发生了变化，被指向为 ListNode1。然后我们把栈内存中的 curr 也指向为 ListNode1。

其实通过这一步我们就已经知道整个代码的目的了。curr 被当成一个指针，一直指向每次循环新生成的 ListNode。下一次循环的时候，也就是 STEP 2 ，可以发现此时 curr 指向为 ListNode1，curr.next 也就是 ListNode1.next 指向为新生成的 ListNode2。

在整个循环中，可以发现唯一不变的就是 head 了，它一直指向的都是最初的 ListNode ，变化的是 ListNode.next ，循环结束后，这个链就串起来了。

最后通过 head.next 就得到我们想要的链表了。

同理，用这种方法去解答类似 Leetcode 两数相加的问题，可以把它的难度由中等降为简单。

奇偶链表

下一个例子是奇偶链表，这道题在 leetcode 中是一道中等难度的题目，通过画图的方式会发现其实十分简单。

题目描述如下：

这道题的代码也是十分简单的，但是直接看代码感觉是一脸懵逼。

const oddEvenList = (head) => {  if (head == null) {    return null  }  let odd = head, even = head.next, evenHead = even;  while (even != null && even.next != null) {    odd.next = even.next    odd = odd.next    even.next = odd.next    even = even.next  }  odd.next = evenHead  return head};

下面，我们通过图解的方式来解析这道题的代码。

首先，我们准备好测试用例。根据链表的长度，我们可以写出三个测试用例。

# 空链表null# 链表节点个数为奇数1->2->3->4->5->NULL# 链表节点个数为偶数1->2->3->4->5->6->NULL

得到测试用例后，我们先可以把异常情况处理了，就是空链表的情况。

if (head == null) {    return null}

然后，分别画出链表节点个数为奇数和偶数情况下的过程。

链表节点个数为奇数

链表节点个数为偶数

画完图了，我们再根据图解来写代码就很好写了。

首先是声明奇偶链表的头尾节点。也就是图 1 和图 2 的 STEP 0

let odd = head, even = head.next, evenHead = even;

然后我们看 while 循环的结束条件，图 1 的 STEP 2，当 even == null 就结束了；图 2 的 STEP 2，当 even.next == null 就结束了。所以综合起来，也就是下面的代码：

while (even != null && even.next != null) {}

评论区很多人对官方解法的这一步不是很明确，为什么循环的结束条件是这个？用图解的方式是不是就很明确了？

我们再来看循环的结构体代码：

odd.next = even.nextodd = odd.nexteven.next = odd.nexteven = even.next

我们可以看 STEP 0 到 STEP 1 的变化，就是把节点 2 拿到了偶数链表，奇数链表的节点 1 指向节点 3 。我们分别操作这两个链表的指针。

首先奇数链表把 odd.next 指向 even.next ，也就是 1->3 ，然后指针后移一位：odd = odd.next

odd.next = even.nextodd = odd.next

奇数链表的操作完了，我们再来操作偶数链表。我们需要完成 2->4 ，也就是 even.next = odd.next 。

因为上一步操作奇数链表后 odd 已经指向了 3 。同样指针后移一位：even = even.next

even.next = odd.nexteven = even.next

从 STEP 1 到 STEP 2 也是在重复这个过程。最后我们看 FINAL 这一步，把偶数链表接到奇数链表的后面。也就是 5->2。

odd.next = evenHead

最后返回 head 节点，就是改变之后的链表了。

后记

Leetcode 的官方题解有一句话我十分赞同：解决链表问题最好的办法是在脑中或者纸上把链表画出来

在脑中去模拟的话比较困难，那我们就在纸上用草图画一画吧。很多类似的算法问题都迎刃而解。