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
然后再添加反向的引用链,思路巧妙无法言喻。