题目地址

  • 🤬 第一次练习 2020å¹´3月10日
  • 😃 第二次练习 2020å¹´3月14日 第一次练习还是很懵的,参考了人家的题解,加上反复练习,终于还是比较清晰了
  • 👍 第三次练习 2020å¹´3月17日 差点忘记,最后记起双指针,才写出来。
  • 👍 第四次练习 2020å¹´5月18日 再次回顾递归

对于递归算法,最重要的就是明确递归函数的定义。具体来说,我们的 reverse 函数定义是这样的:

输入一个节点 head,将「以 head 为起点」的链表反转,并返回反转之后的头结点。

明白了函数的定义,在来看这个问题。比如说我们想反转这个链表:

image-20200518201157000

那么输入 reverse(head) 后,会在这里进行递归:

ListNode last = reverse(head.next);

不要跳进递归(你的脑袋能压几个栈呀?),而是要根据刚才的函数定义,来弄清楚这段代码会产生什么结果:

image-20200518201219298

这个 reverse(head.next) 执行完成后,整个链表就成了这样:

image-20200518201238324

并且根据函数定义,reverse 函数会返回反转之后的头结点,我们用变量 last 接收了。

现在再来看下面的代码:

head.next.next = head;
image-20200518201248819

接下来:

head.next = null;
return last;
image-20200518201258728

神不神奇,这样整个链表就反转过来了!递归代码就是这么简洁优雅,不过其中有两个地方需要注意:

1、递归函数要有 base case,也就是这句:

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

意思是如果链表只有一个节点的时候反转也是它自己,直接返回即可。

2、当链表递归反转之后,新的头结点是 last,而之前的 head 变成了最后一个节点,别忘了链表的末尾要指向 null:

head.next = null;

# 双指针解法

WARNING

我居然看到自己以前通过过,但是现在一点理解不到。💀

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    /**
     * 定义三个变量  prev, cur, next
     * prev 执行已经翻转的链表部分
     * cur, next 指向即将要翻转链表部分的头节点
     * loop next = cur.next; cur.next = prev; // 翻转链表之后
     * 更新指针, prev, cur 都向前移动
     * prev = cur;
     * cur = next;
     **/

     let prev = null, cur = head, next = head;
     while(cur != null) {
         next = cur.next;
         cur.next = prev;
         prev = cur;
         cur = next;
     }

     return prev;
};

# 递归写法

public ListNode reverseList(ListNode head) {
    /**
         * 递归求解
         * 1. 处理 base base | if head.next == null return
         * 2. 翻转后的链表 指向现有的头节点
         * 3. 现有头节点 next 置空
         */

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

    ListNode last = reverseList(head.next);
    head.next.next = head;
    head.next = null;

    return last;
}

# 利用 ES6 的另类写法,不过内存占用较高🐂

/*
 * @lc app=leetcode.cn id=206 lang=javascript
 *
 * [206] 反转链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
  let [prev, curr] = [null, head];

  while (curr) {
    [curr.next, prev, curr] = [prev, curr, curr.next];
  }

  return prev;
};
// @lc code=end

最后编辑时间: 7/14/2020, 9:21:47 AM