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

 关注

发布于: 2020 年 07 月 01 日

这周在刷链表的算法时，发现对于这类问题用图解的方式来解决十分简单。通常我们的草图画完了，代码也就随之写出来了，不用绞尽脑汁去想 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 = head
curr.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.next
odd = odd.next
even.next = odd.next
even = even.next
﻿
我们可以看 STEP 0 到 STEP 1 的变化，就是把节点 2 拿到了偶数链表，奇数链表的节点 1 指向节点 3 。我们分别操作这两个链表的指针。
﻿
首先奇数链表把 odd.next 指向 even.next ，也就是 1->3 ，然后指针后移一位：odd = odd.next
﻿
odd.next = even.next
odd = odd.next
﻿
奇数链表的操作完了，我们再来操作偶数链表。我们需要完成 2->4 ，也就是 even.next = odd.next 。
因为上一步操作奇数链表后 odd 已经指向了 3 。同样指针后移一位：even = even.next
﻿
even.next = odd.next
even = even.next
﻿
从 STEP 1 到 STEP 2 也是在重复这个过程。最后我们看 FINAL 这一步，把偶数链表接到奇数链表的后面。也就是 5->2。
﻿
odd.next = evenHead
﻿
最后返回 head 节点，就是改变之后的链表了。
﻿
后记﻿
Leetcode 的官方题解有一句话我十分赞同：解决链表问题最好的办法是在脑中或者纸上把链表画出来
﻿
在脑中去模拟的话比较困难，那我们就在纸上用草图画一画吧。很多类似的算法问题都迎刃而解。
﻿