[LeetCode-206反转链表] | 刷题打卡

掘金团队号上线，助你 Offer 临门！ 点击 查看详情

题目描述

反转一个单链表。 进阶： 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

解题思路

两种方式：

1. 指针法，如图示：

这个思路比较好理解，我们需要定义三个指针：

• 定义指针pre，指向空
• 定义指针cur，为待反转区头节点
• 定义指针next，为cur.next
• cur.next指向pre, pre = cur, cur = cur.next;

2. 递归

递归最忌讳的就是在你的大脑中把递归展开，展开的话，大脑就会陷入混乱。递归的写法我写在下面，然后在代码里写注释，说明每行的意思。

解题代码

// 指针法
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做的，做了一下午。。。。