迭代和递归 - leetcode 206. Reverse Linked List

2015-08-18 10:39:00 浏览：1579 作者：管理员

Reverse Linked List，一道有趣的题目。给你一个链表，输出反向链表。因为我用的是JavaScript提交，所以链表的每个节点都是一个对象。例如1->2->3，就要得到3->2->1。

1、数组构造

一个很容易想到的方法是用数组保存新构造每个节点，然后反向构造链表，输出：

var reverseList = function(head) {  var ans = [];  while (head) {    var node = new ListNode(head.val);    ans.push(node);    head = head.next;  }  ans.reverse();  if (!ans.length)    return null;  for (var i = 0, len = ans.length; i < len - 1; i++) {    ans[i].next = ans[i + 1];  }  return ans[0];};

虽然能AC，但是浪费了空间，我们幻想能不能直接把指针指向扭转过来？

2、迭代

迭代的精髓在于按顺序对指针指向的扭转。以1->2->3->4为例，当迭代到第三次时，前面的运算已经保存了一个pre值，值为2->1，这时到3这个节点，只需把它的指向指到pre即可，而构成的新的链表3->2->1保存为pre以供下次迭代，但是因为它后面的值还要做运算，所以把它原先的指向先保存起来（为next），为了下次继续迭代：

var reverseList = function(head) {  var pre = null;  while (head) {    var next = head.next;    head.next = pre;    pre = head;    head = next;  }  return pre;};

3、递归

递归是迭代的好兄弟，这道题的递归很巧妙，想起来也有点复杂。

var reverseList = function(head) {  if (head === null || head.next === null)    return head;  var next = head.next;  head.next = null;  var newHead = reverseList(next);  next.next = head;  return newHead;};

递归的精髓在于将next当做参数传入reverseList函数时，在下一次递归中对参数的操作，会反应在上次的参数值上。

还是以1->2->3->4举例子，4次递归后（回溯前），其实是将引用链全部打破：

1      2      3      4|      |      |      |null   null  null   null

然后再添加反向的引用链，思路巧妙无法言喻。