[LeetCode-206反转链表] | 刷题打卡
分类:javascript
掘金团队号上线,助你 Offer 临门! 点击 查看详情
题目描述
反转一个单链表。
进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题?
解题思路
两种方式:
- 指针法,如图示:
这个思路比较好理解,我们需要定义三个指针:
- 定义指针pre,指向空
- 定义指针cur,为待反转区头节点
- 定义指针next,为cur.next
- cur.next指向pre, pre = cur, cur = cur.next;
- 递归
递归最忌讳的就是在你的大脑中把递归展开,展开的话,大脑就会陷入混乱。递归的写法我写在下面,然后在代码里写注释,说明每行的意思。
解题代码
// 指针法
var reverseList = function (head) {
if (!head || !head.next) return head;
let [pre, cur, p] = [null, head, head.next];
while (cur) {
[cur.next, pre, cur] = [pre, cur, cur.next]
}
return pre;
};
// 递归法
var reverseListFn = function (head) {
if (!head || !head.next) return head;
// 这个p值一定是head.next = 链表最末尾,返回链表尾节点
let tail = head.next, p = reverserListFn(head.next);
// 这句是为了让链表后一位指向前一位
tail.next = head;
// 这里是为了断开原来链表的连接,避免形成环形链表
head.next = null;
return p;
};
总结
递归千万不要在自己脑海里展开......后面我会做一系列二叉树的题目,更好的去理解递归思想。
对了,这里补充一下,写这篇我用了很久的时间,因为我不会做动图,上面的指针法的动图是自己用ppt做的,做了一下午。。。。