在昨天的文章中提到,循环是一个正向线性思维,但是递归确实一种一种为始的反向思维。多数人习惯与正向思维,因为反向思维实际上有点儿反本能的,但是往往反向思维却能很好地解决一些看上去复杂正向思维难以解决的问题,比如汉诺塔问题。

今天以一个常见的算法面试题,来对比循环和递归在代码上的差别,以及为什么更推荐递归的写法以简化代码。这个常见的算法面试题,就是反转链表(https//leetcode-cn.com/problems/reverse-linked-list/)。

image.png

准备工作


为了方便起见,可以打开浏览器,F12 进入开发控制台,使用 JavaScript 来实现和验证。首先写一些帮助函数来方便自动化测试: javascript function test(expect, sut, message) { console.log(message)

let sutString = linkToArray(sut).join(->); let actual = reverseLink(sut); let left = linkToArray(expect).join(->); let right = linkToArray(actual).join(->);

if(left === right){ console.log(tt + left + == revert( + sutString + ) PASS); } else { console.error(tt + left + == revert( + sutString + ) FAIL); } }

function linkToArray(head){ const res = []; let set = new Set();

while(head) { if(set.has(head)) { res.push(loop!); return res; }

res.push(head.val);    
set.add(head);
head = head.next;

}

return res; }


然后,将设计好的测试用例列出来: javascript // 测试用例: test(null, reverseLink(null), 测试 null)

let headA = {val 1, next null} test(headA, (headA), 测试一个节点)

headA.next = {val 2, next null}; let reversed = {val 2, next {val 1, next null}} test(reversed, (headA), 测试两个节点);

headA = {val 1, next {val 2, next {val 3, next null }}} reversed = {val 3, next {val 2, next {val 1, next null }}} test(reversed, (headA), 测试三个节点);

let cycle = {val 1, next null} cycle.next = cycle;

test(cycle, (cycle), 测试指向自己的一个节点的循环链表); console.assert(linkToArray(cycle).join(->) === 1->loop!, cycle);

let next = {val 2, next null}; cycle.next = next; next.next = cycle;

test(next, (cycle), 测试两个互相指向的节点组成的循环链表); console.assert(linkToArray(cycle).join(->) === 1->2->loop!, cycle);

next = {val 3, nextnull}; cycle = {val 1, next {val 2, next next}} next.next = cycle;

test(next, (cycle), 测试由三个节点组成的循环链表);

循环实现


比较容易想到的方案就是从头开始循环,每次对前后节点的指针进行倒转。在实现过程中,会发现指针的倒转,需要特别注意。 javascript // 假设不存在重复节点 function reverseLink(head) { if(head === null) { return head; }

let prev = head;

let next = prev.next; prev.next = null;

while(prev && next) { let temp = next.next; next.next = prev; prev = next; next = temp;

if(next === head) {
  head.next = prev;
  return prev;
}

}

return prev; }

注意以上 while 循环体中,开头 4 行的顺序特别重要!顺序错误就会导致程序 BUG。将以上实现和测试用例在开发者控制面板中运行,测试全部通过:

递归实现


递归实现的关键在于思考方式,你要设想一个小一点的问题,已经被解决了。在这里,可以设想除了头节点,从下一个节点开始到末尾的子链表已经被反转了,这时候,只需要将关注点放在如何将头节点放置到子链表的末尾,这样就实现了整个链表的反转:

javascript /**

  • Definition for singly-linked list.
  • function ListNode(val) {
  • this.val = val;
  • this.next = null;
  • } */ /**
  • @param {ListNode} head
  • @return {ListNode} */ var reverseList = function(head) { if(!head){ return null; }

    if(head.next === null){ return head; }

    const rev = reverseList(head.next); head.next.next = head; head.next = null;

    return rev; };

可以看出,除了一些边界检查和循环类似之外,主要逻辑简单了很多!将头节点放置在已经被反转的子链表之后,这个逻辑很自然,因此代码上没有需要特别注意的地方。这个实现和测试结果可以参见:https//leetcode-cn.com/submissions/detail/43900191/

但是要注意的是,在循环实现中,支持了环链表(参见后面的测试用例)。如果要让递归实现也支持环链表,需要再做一些改进:
javascript var reverseList = function(head) { return ((head, cycleStart) { if(!head){ return null; }

if(head.next === null || head.next === head){
    return head;
}

if (head.next === cycleStart) {
  return head;
}

const rev = reverseList(head.next, cycleStart);
head.next.next = head;

if(!cycleStart) { head.next = null; } else { head.next = rev; }

return rev;

})(head, head); };

彩蛋


递归方式会导致一个问题,相同的操作会做很多次。有一个简单粗暴的改进方案,就是使用空间换时间,不需要改动实现代码,只要使用前面文章中介绍过的 memoized 将其包装起来即可。 javascript const reverseList = memoized( (head) => { return ((head, cycleStart) { if(!head){ return null; }

  if(head.next === null || head.next === head){
      return head;
  }

  if (head.next === cycleStart) {
    return head;
  }

  const rev = reverseList(head.next, cycleStart);
  head.next.next = head;

  if(!cycleStart) {
    head.next = null;
  } else {
    head.next = rev;
  }

  return rev;

})(head, head); } );

完整的代码和测试见:https//github.com/Jeff-Tian/JobInterviewTests/blob/dev/ByteDance/src/reverseList.ts