Info
新版网站会员 即将涨价;已支持老用户续费~
读完本文,你不仅学会了算法套路,还可以顺便解决如下题目:
LeetCode | 力扣 | 难度 |
---|---|---|
206. Reverse Linked List | 206. 反转链表 | 🟢 |
92. Reverse Linked List II | 92. 反转链表 II | 🟠 |
- | 剑指 Offer 24. 反转链表 | 🟢 |
- | 剑指 Offer II 024. 反转链表 | 🟢 |
反转单链表的迭代实现不是一个困难的事情,但是递归实现就有点难度了,如果再加一点难度,让你仅仅反转单链表中的一部分,你是否能够递归实现呢?
提示
迭代反转单链表的实现参见 如何 k 个一组反转链表。
本文就来由浅入深,step by step 地解决这个问题。如果你还不会递归地反转单链表也没关系,本文会从递归反转整个单链表开始拓展,只要你明白单链表的结构,相信你能够有所收获。
// 单链表节点的结构
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
// 单链表节点的结构
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
# 单链表节点的结构
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
// ListNode - 单链表节点的结构
type ListNode struct {
val int
next *ListNode
}
// NewListNode - 创建一个新的节点
func NewListNode(x int) *ListNode {
return &ListNode{val: x}
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
// 单链表节点的结构
var ListNode = function(x) {
this.val = x;
this.next = null;
}
什么叫反转单链表的一部分呢,就是给你一个索引区间,让你把单链表中这部分元素反转,其他部分不变。
看下力扣第 92 题「反转链表 II」:
92. 反转链表 II | 力扣 | LeetCode |
head
和两个整数 left
和 right
,其中 left <= right
。请你反转从位置 left
到位置 right
的链表节点,返回 反转后的链表 。
示例 1:
输入:head = [1,2,3,4,5], left = 2, right = 4 输出:[1,4,3,2,5]
示例 2:
输入:head = [5], left = 1, right = 1 输出:[5]
提示:
- 链表中节点数目为
n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n
进阶: 你可以使用一趟扫描完成反转吗?
注意这里的索引是从 1 开始的。迭代的思路大概是:先用一个 for 循环找到第 m
个位置,然后再用一个 for 循环将 m
和 n
之间的元素反转。但是我们的递归解法不用一个 for 循环,纯递归实现反转。
迭代实现思路看起来虽然简单,但是细节问题很多的,反而不容易写对。相反,递归实现就很简洁优美,下面就由浅入深,先从反转整个单链表说起。
一、递归反转整个链表
这也是力扣第 206 题「反转链表」,递归反转单链表的算法可能很多读者都听说过,这里详细介绍一下,直接看代码实现:
class Solution {
// 定义:输入一个单链表头结点,将该链表反转,返回新的头结点
public ListNode reverse(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode last = reverse(head.next);/**<extend up -200><div class="img-content"><img src="/algo/images/反转链表/3.jpg" class="myimage"/></div> */
head.next.next = head;/**<extend up -200><div class="img-content"><img src="/algo/images/反转链表/4.jpg" class="myimage"/></div> */
head.next = null;/**<extend up -200><div class="img-content"><img src="/algo/images/反转链表/5.jpg" class="myimage"/></div> */
return last;
}
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
class Solution {
public:
// 定义:输入一个单链表头结点,将该链表反转,返回新的头结点
ListNode* reverse(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* last = reverse(head->next);/**<extend up -200><div class="img-content"><img src="/algo/images/反转链表/3.jpg" class="myimage"/></div> */
head->next->next = head;/**<extend up -200><div class="img-content"><img src="/algo/images/反转链表/4.jpg" class="myimage"/></div> */
head->next = nullptr;/**<extend up -200><div class="img-content"><img src="/algo/images/反转链表/5.jpg" class="myimage"/></div> */
return last;
}
};
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
class Solution:
# 定义:输入一个单链表头结点,将该链表反转,返回新的头结点
def reverse(self, head):
if head is None or head.next is None:
return head
last = self.reverse(head.next)
#<extend up -200>
#<div class="img-content"><img src="/images/反转链表/3.jpg" class="myimage"/></div>
head.next.next = head
#<extend up -200>
#<div class="img-content"><img src="/images/反转链表/4.jpg" class="myimage"/></div>
head.next = None
#<extend up -200>
#<div class="img-content"><img src="/images/反转链表/5.jpg" class="myimage"/></div>
return last
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
// Definition for singly-linked list.
type ListNode struct {
Val int
Next *ListNode
}
// reverse 定义:输入一个单链表头结点,将该链表反转,返回新的头结点
func reverse(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
last := reverse(head.Next)/**<extend up -200><div class="img-content"><img src="/algo/images/反转链表/3.jpg" class="myimage"/></div> */
head.Next.Next = head/**<extend up -200><div class="img-content"><img src="/algo/images/反转链表/4.jpg" class="myimage"/></div> */
head.Next = nil/**<extend up -200><div class="img-content"><img src="/algo/images/反转链表/5.jpg" class="myimage"/></div> */
return last
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
var reverse = function(head) {
// Define: enter a single linked list head node, reverse this list, and return the new head node
if (head == null || head.next == null) {
return head;
}
var last = reverse(head.next);
/*
<extend up -200>
<div class="img-content"><img src="/images/反转链表/3.jpg" class="myimage"/></div>
*/
head.next.next = head;
/*
<extend up -200>
<div class="img-content"><img src="/images/反转链表/4.jpg" class="myimage"/></div>
*/
head.next = null;
/*
<extend up -200>
<div class="img-content"><img src="/images/反转链表/5.jpg" class="myimage"/></div>
*/
return last;
}
看起来是不是感觉不知所云,完全不能理解这样为什么能够反转链表?这就对了,这个算法常常拿来显示递归的巧妙和优美,我们下面来详细解释一下这段代码。
对于递归算法,最重要的就是明确递归函数的定义。具体来说,我们的 reverse
函数定义是这样的:
输入一个节点 head
,将「以 head
为起点」的链表反转,并返回反转之后的头结点。
明白了函数的定义,再来看这个问题。比如说我们想反转这个链表:
那么输入 reverse(head)
后,会在这里进行递归:
ListNode last = reverse(head.next);
不要跳进递归(你的脑袋能压几个栈呀?),而是要根据刚才的函数定义,来弄清楚这段代码会产生什么结果:
这个 reverse(head.next)
执行完成后,整个链表就成了这样:
并且根据函数定义,reverse
函数会返回反转之后的头结点,我们用变量 last
接收了。
现在再来看下面的代码:
head.next.next = head;
接下来:
head.next = null;
return last;
神不神奇,这样整个链表就反转过来了!递归代码就是这么简洁优雅,不过其中有两个地方需要注意:
1、递归函数要有 base case,也就是这句:
if (head == null || head.next == null) {
return head;
}
意思是如果链表为空或者只有一个节点的时候,反转结果就是它自己,直接返回即可。
2、当链表递归反转之后,新的头结点是 last
,而之前的 head
变成了最后一个节点,别忘了链表的末尾要指向 null:
head.next = null;
理解了这两点后,我们就可以进一步深入了,接下来的问题其实都是在这个算法上的扩展。
二、反转链表前 N 个节点
这次我们实现一个这样的函数:
// 将链表的前 n 个节点反转(n <= 链表长度)
ListNode reverseN(ListNode head, int n)
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
// 将链表的前 n 个节点反转(n <= 链表长度)
ListNode* reverseN(ListNode* head, int n);
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
# 将链表的前 n 个节点反转(n <= 链表长度)
def reverseN(head: ListNode, n: int):
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
// 将链表的前 n 个节点反转(n <= 链表长度)
func ReverseN(head *ListNode, n int) *ListNode {
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
/**
* 将链表的前 n 个节点反转(n <= 链表长度)
*/
var reverseN = function(head, n) {
// TODO: implement function body here
};
比如说对于下图链表,执行 reverseN(head, 3)
:
解决思路和反转整个链表差不多,只要稍加修改即可:
ListNode successor = null; // 后驱节点
// 反转以 head 为起点的 n 个节点,返回新的头结点
ListNode reverseN(ListNode head, int n) {
if (n == 1) {
// 记录第 n + 1 个节点
successor = head.next;
return head;
}
// 以 head.next 为起点,需要反转前 n - 1 个节点
ListNode last = reverseN(head.next, n - 1);
head.next.next = head;
// 让反转之后的 head 节点和后面的节点连起来
head.next = successor;
return last;/**<extend up -90><div class="img-content"><img src="/algo/images/反转链表/7.jpg" class="myimage"/></div> */
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
ListNode* successor = nullptr; // 后驱节点
// 反转以 head 为起点的 n 个节点,返回新的头结点
ListNode* reverseN(ListNode* head, int n) {
if (n == 1) {
// 记录第 n + 1 个节点
successor = head->next;
return head;
}
// 以 head.next 为起点,需要反转前 n - 1 个节点
ListNode* last = reverseN(head->next, n - 1);
head->next->next = head;
// 让反转之后的 head 节点和后面的节点连起来
head->next = successor;
return last;
}
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
successor = None # 后驱节点
# 反转以 head 为起点的 n 个节点,返回新的头结点
def reverseN(head: ListNode, n: int):
global successor
if n == 1:
# 记录第 n + 1 个节点
successor = head.next
return head
# 以 head.next 为起点,需要反转前 n - 1 个节点
last = reverseN(head.next, n - 1)
head.next.next = head
# 让反转之后的 head 节点和后面的节点连起来
head.next = successor
return last
# <div class="img-content"><img src="/images/反转链表/7.jpg" class="myimage"/></div>
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
var successor *ListNode // 后驱节点
// 反转以 head 为起点的 n 个节点,返回新的头结点
func reverseN(head *ListNode, n int) *ListNode {
if n == 1 {
// 记录第 n + 1 个节点
successor = head.Next
return head
}
// 以 head.Next 为起点,需要反转前 n - 1 个节点
last := reverseN(head.Next, n - 1)
head.Next.Next = head
// 让反转之后的 head 节点和后面的节点连起来
head.Next = successor
return last/**<extend up -90><div class="img-content"><img src="/algo/images/反转链表/7.jpg" class="myimage"/></div> */
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
var successor = null; // 后驱节点
// 反转以 head 为起点的 n 个节点,返回新的头结点
var reverseN = function(head, n) {
if (n == 1) {
// 记录第 n + 1 个节点
successor = head.next;
return head;
}
// 以 head.next 为起点,需要反转前 n - 1 个节点
var last = reverseN(head.next, n - 1);
head.next.next = head;
// 让反转之后的 head 节点和后面的节点连起来
head.next = successor;
return last;
}
具体的区别:
1、base case 变为 n == 1
,反转一个元素,就是它本身,同时要记录后驱节点。
2、刚才我们直接把 head.next
设置为 null,因为整个链表反转后原来的 head
变成了整个链表的最后一个节点。但现在 head
节点在递归反转之后不一定是最后一个节点了,所以要记录后驱 successor
(第 n + 1
个节点),反转之后将 head
连接上。
OK,如果这个函数你也能看懂,就离实现「反转一部分链表」不远了。
三、反转链表的一部分
现在解决我们最开始提出的问题,给一个索引区间 [m, n]
(索引从 1 开始),仅仅反转区间中的链表元素。
ListNode reverseBetween(ListNode head, int m, int n)
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
ListNode* reverseBetween(ListNode* head, int m, int n)
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
def reverseBetween(head: ListNode, m: int, n: int) -> ListNode:
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
func reverseBetween(head *ListNode, m int, n int) *ListNode
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
var reverseBetween = function(head, m, n) {
};
首先,如果 m == 1
,就相当于反转链表开头的 n
个元素嘛,也就是我们刚才实现的功能:
ListNode reverseBetween(ListNode head, int m, int n) {
// base case
if (m == 1) {
// 相当于反转前 n 个元素
return reverseN(head, n);
}
// ...
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
ListNode* reverseBetween(ListNode* head, int m, int n) {
// base case
if (m == 1) {
// 相当于反转前 n 个元素
return reverseN(head, n);
}
// ...
}
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
# base case
if m == 1:
# 相当于反转前 n 个元素
return self.reverseN(head, n)
#...
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
func reverseBetween(head *ListNode, m int, n int) *ListNode {
// base case
if m == 1 {
// 相当于反转前 n 个元素
return reverseN(head, n)
}
// ...
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
var reverseBetween = function(head, m, n) {
// base case
if (m == 1) {
// 相当于反转前 n 个元素
return reverseN(head, n);
}
// ...
}
如果 m != 1
怎么办?如果我们把 head
的索引视为 1,那么我们是想从第 m
个元素开始反转对吧;如果把 head.next
的索引视为 1 呢?那么相对于 head.next
,反转的区间应该是从第 m - 1
个元素开始的;那么对于 head.next.next
呢……
区别于迭代思想,这就是递归思想,所以我们可以完成代码:
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
// base case
if (m == 1) {
return reverseN(head, n);
}
// 前进到反转的起点触发 base case
head.next = reverseBetween(head.next, m - 1, n - 1);
return head;
}
// 后驱节点
ListNode successor = null;
// 反转以 head 为起点的 n 个节点,返回新的头结点
ListNode reverseN(ListNode head, int n) {
if (n == 1) {
// 记录第 n + 1 个节点
successor = head.next;
return head;
}
ListNode last = reverseN(head.next, n - 1);
head.next.next = head;
head.next = successor;
return last;
}
}
// 注意:cpp 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
class Solution {
public:
// 后驱节点
ListNode* successor = nullptr;
// 反转以 head 为起点的 n 个节点,返回新的头结点
ListNode* reverseN(ListNode* head, int n) {
if (n == 1) {
// 记录第 n + 1 个节点
successor = head->next;
return head;
}
ListNode* last = reverseN(head->next, n - 1);
head->next->next = head;
head->next = successor;
return last;
}
ListNode* reverseBetween(ListNode* head, int m, int n) {
// base case
if (m == 1) {
return reverseN(head, n);
}
// 前进到反转的起点触发 base case
head->next = reverseBetween(head->next, m - 1, n - 1);
return head;
}
};
# 注意:python 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
class Solution:
# 后驱节点
successor = None
def reverseBetween(self, head, m, n):
"""
:type head: ListNode
:type m: int
:type n: int
:rtype: ListNode
"""
# base case
if m == 1:
return self.reverseN(head, n)
# 前进到反转的起点触发 base case
head.next = self.reverseBetween(head.next, m - 1, n - 1)
return head
# 反转以 head 为起点的 n 个节点,返回新的头结点
def reverseN(self, head, n):
if n == 1:
# 记录第 n + 1 个节点
self.successor = head.next
return head
last = self.reverseN(head.next, n - 1)
head.next.next = head
head.next = self.successor
return last
// 注意:go 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
// ListNode for singly-linked list
type ListNode struct {
Val int
Next *ListNode
}
func reverseBetween(head *ListNode, m int, n int) *ListNode {
var reverse func(*ListNode) (*ListNode, *ListNode)
// 反转以 head 为起点的 n 个节点,返回新的头结点
reverse = func(head *ListNode, n int) (*ListNode, *ListNode) {
if n == 1 {
// 记录第 n + 1 个节点
successor := head.Next
return head, successor
}
last, successor := reverse(head.Next, n-1)
head.Next.Next = head
head.Next = successor
return last, successor
}
// base case
if m == 1 {
newHead, _ := reverse(head, n)
return newHead
}
// 前进到反转的起点触发 base case
head.Next = reverseBetween(head.Next, m-1, n-1)
return head
}
// 注意:javascript 代码由 chatGPT🤖 根据我的 java 代码翻译,旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性,仅供参考。如有疑惑,可以参照我写的 java 代码对比查看。
// Initialize a new ListNode class for JavaScript
function ListNode(val, next) {
this.val = (val===undefined ? 0 : val)
this.next = (next===undefined ? null : next)
}
var reverseBetween = function(head, m, n) {
var successor = null;
function reverseN(head, n) {
if (n == 1) {
// 记录第 n + 1 个节点
successor = head.next;
return head;
}
var last = reverseN(head.next, n - 1);
head.next.next = head;
head.next = successor;
return last;
}
// base case
if (m == 1) {
return reverseN(head, n);
}
// 前进到反转的起点触发 base case
head.next = reverseBetween(head.next, m - 1, n - 1);
return head;
}
四、最后总结
递归的思想相对迭代思想,稍微有点难以理解,处理的技巧是:不要跳进递归,而是利用明确的定义来实现算法逻辑。
处理看起来比较困难的问题,可以尝试化整为零,把一些简单的解法进行修改,解决困难的问题。
值得一提的是,递归操作链表并不高效。和迭代解法相比,虽然时间复杂度都是 O(N),但是迭代解法的空间复杂度是 O(1),而递归解法需要堆栈,空间复杂度是 O(N)。所以递归操作链表可以作为对递归算法的练习或者拿去和小伙伴装逼,但是考虑效率的话还是使用迭代算法更好。
引用本文的文章
引用本文的题目
安装 我的 Chrome 刷题插件 点开下列题目可直接查看解题思路:
LeetCode | 力扣 |
---|---|
2. Add Two Numbers | 2. 两数相加 |
445. Add Two Numbers II | 445. 两数相加 II |
- | 剑指 Offer 24. 反转链表 |
- | 剑指 Offer II 024. 反转链表 |
- | 剑指 Offer II 025. 链表中的两数相加 |
《labuladong 的算法笔记》已经出版,关注公众号查看详情;后台回复「全家桶」可下载配套 PDF 和刷题全家桶: