【LeetCode】图解反转链表 - 迭代 - 递归

语言: CN / TW / HK

theme: fancy highlight: a11y-dark


嗨!~ 大家好,我是YK菌 🐷 ,一个微系前端 ✨,喜欢分享自己学到的小知识 🏹,欢迎关注我呀 😘 ~ [微信号: yk2012yk2012,微信公众号:ykyk2012]

「这是我参与11月更文挑战的第6天,活动详情查看:2021最后一次更文挑战

今天来一道特别经典也是特别高频的题,反转链表。我们分别使用递归与非递归的方式来解决这道题,但是这里递归的方式比较难理解,需要好好思考,可以帮助我们刚好的了解递归的思想

206. 反转链表

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

image.png

【解法一】非递归

这里是反转链表不是反转数组,所以我们直接修改结点之间的指针就可以实现反转链表的操作了!

举一个链表的例子:3 -> 2 -> 1 ,我们先反转前两个结点的指针关系,得到 3 <- 2 -> 1 , 此时我们再反转后面的指针得到 3 <- 2 <- 1 此时我们就将链表反转了,顺序遍历的话就是 1 -> 2 -> 3

  1. 初始化

js let prev = null; let curr = head;

image.png

那我们现就只需要聚焦在如何改变两个结点之间的指针即可

  1. 指针反转

js let temp = curr.next; curr.next = prev;

image.png

  1. 后移指针 js prev = curr; curr = temp; image.png

  2. 一次的结果

image.png

循环遍历反转所有指针即可

javascript var reverseList = function(head) { let prev = null; let curr = head; while (curr) { let temp = curr.next; curr.next = prev; prev = curr; curr = temp; } return prev; };

用一个动图演示就是这样 动图链接

image.png

最后来看看结果

image.png

【解法二】递归

我们这样思考,一个链表,如果在某个位置,后面部分都已经反转了,那它前面部分怎么操作

image.png

采用递归的方式来解题,从头结点开始递归到底,递归出口就是最后一个结点。最后一个节点作为反转后的头节点。

然后就是在每一层递归种进行反转的操作,动图如下

动图链接

image.png

```javascript var reverseList = function(head) { // 递归出口,返回最后一个节点作为反转后的头结点 if (head == null || head.next == null) { return head; }

// 新头结点newHead指向尾结点,此处进入递归,递归一直到遍历到尾结点时才会返回
const newHead = reverseList(head.next);

// 每一层递归操作,让head的下一个节点指向自己【反转】
head.next.next = head;
// head指向null。以此达到反转的目的。
head.next = null;

return newHead;

}; ```

image.png

最后,欢迎关注我的专栏,和YK菌做好朋友~

「其他文章」