递归魔法：反转单链表

labuladong约 6835 字大约 23 分钟数据结构递归链表

Info

数据结构精品课open in new window 和递归算法专题课open in new window 限时附赠网站会员，全新纸质书《labuladong 的算法笔记》open in new window 出版，签名版限时半价！

读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：

LeetCode	力扣	难度
206. Reverse Linked Listopen in new window	206. 反转链表open in new window	🟢
92. Reverse Linked List IIopen in new window	92. 反转链表 IIopen in new window	🟠
-	剑指 Offer 24. 反转链表open in new window	🟢
-	剑指 Offer II 024. 反转链表open in new window	🟢

反转单链表的迭代实现不是一个困难的事情，但是递归实现就有点难度了，如果再加一点难度，让你仅仅反转单链表中的一部分，你是否能够递归实现呢？

Tip

迭代反转单链表的实现参见如何 k 个一组反转链表。

本文就来由浅入深，step by step 地解决这个问题。如果你还不会递归地反转单链表也没关系，本文会从递归反转整个单链表开始拓展，只要你明白单链表的结构，相信你能够有所收获。

// 单链表节点的结构
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 单链表节点的结构
class ListNode {
public:
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

# 单链表节点的结构
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 单链表节点的结构
type ListNode struct {
    Val int
    Next *ListNode
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 单链表节点的结构
var ListNode = function(val) {
    this.val = val;
    this.next = null;
}

什么叫反转单链表的一部分呢，就是给你一个索引区间，让你把单链表中这部分元素反转，其他部分不变。

看下力扣第 92 题「反转链表 IIopen in new window」：

注意这里的索引是从 1 开始的。迭代的思路大概是：先用一个 for 循环找到第 m 个位置，然后再用一个 for 循环将 m 和 n 之间的元素反转。但是我们的递归解法不用一个 for 循环，纯递归实现反转。

迭代实现思路看起来虽然简单，但是细节问题很多的，反而不容易写对。相反，递归实现就很简洁优美，下面就由浅入深，先从反转整个单链表说起。

一、递归反转整个链表

这也是力扣第 206 题「反转链表open in new window」，递归反转单链表的算法可能很多读者都听说过，这里详细介绍一下，直接看代码实现：

// 定义：输入一个单链表头结点，将该链表反转，返回新的头结点
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 代码对比查看。

// 定义：输入一个单链表头结点，将该链表反转，返回新的头结点
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 代码对比查看。

# 定义：输入一个单链表头节点，将该链表反转，返回新的头结点
def reverse(head: ListNode) -> ListNode:
    if not head or not head.next:
        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 = None # <extend up -200><div class="img-content"><img src="/algo/images/反转链表/5.jpg" class="myimage"/></div> #
    return last

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

// 定义：输入一个单链表头结点，将该链表反转，返回新的头结点
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) {
    if (head === null || head.next === null) {
        return head;
    }
    var 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;
};

看起来是不是感觉不知所云，完全不能理解这样为什么能够反转链表？这就对了，这个算法常常拿来显示递归的巧妙和优美，我们下面来详细解释一下这段代码。

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

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

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

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

ListNode last = reverse(head.next);

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

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

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

现在再来看下面的代码：

head.next.next = head;

接下来：

head.next = null;
return last;

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

head->next = nullptr;
return last;

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

head.next = None
return last

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

head.next = nil
return last

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var setNextNodeToNull = function(head) {
    head.next = null;
    return last;
}

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

1、递归函数要有 base case，也就是这句：

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

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

if (head == NULL || head->next == NULL) {
    return head;
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

if head is None or head.next is None:
    return head

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

if head == nil || head.next == nil {
    return head
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

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

意思是如果链表为空或者只有一个节点的时候，反转结果就是它自己，直接返回即可。

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

head.next = null;

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

head->next = NULL;

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

head.next = None

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

head.next = nil

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var 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 <= 链表长度）
function reverseN(head, n) {
  var curr = head;
  var prev = null;
  for (var i = 0; i < n; i++) {
    var next = curr.next;
    curr.next = prev;
    prev = curr;
    curr = next;
  }
  head.next = curr;
  return prev;
}

比如说对于下图链表，执行 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) {
        successor = head->next;
        return head;
    }
    ListNode* last = reverseN(head->next, n - 1);
    head->next->next = head;
    head->next = successor;
    return last;
}

# 注意：python 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
# 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

successor = None # 后继节点

# 反转以 head 为起点的 n 个节点，返回新的头节点
def reverseN(head: ListNode, n: int) -> ListNode:
    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 # <extend up -90><div class="img-content"><img src="/algo/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 个节点，返回新的头结点
function reverseN(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;/**<extend up -90><div class="img-content"><img src="/algo/images/反转链表/7.jpg" class="myimage"/></div> */
}

具体的区别：

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) {
    // function body here
};

首先，如果 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(head: ListNode, m: int, n: int) -> ListNode:
    if m == 1:
        # 相当于反转前 n 个元素
        return 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) {
    // 基线条件，如果m为1，则相当于反转前n个节点
    if (m == 1) {
        return reverseN(head, n);
    }
    // ...
};

如果 m != 1 怎么办？如果我们把 head 的索引视为 1，那么我们是想从第 m 个元素开始反转对吧；如果把 head.next 的索引视为 1 呢？那么相对于 head.next，反转的区间应该是从第 m - 1 个元素开始的；那么对于 head.next.next 呢……

区别于迭代思想，这就是递归思想，所以我们可以完成代码：

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;
}

// 注意：cpp 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

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 代码对比查看。

def reverseBetween(head: ListNode, m: int, n: int) -> ListNode:
    # base case
    if m == 1:
        return reverseN(head, n)
    # 前进到反转的起点触发 base case
    head.next = reverseBetween(head.next, m - 1, n - 1)
    return head

// 注意：go 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

func reverseBetween(head *ListNode, m int, n int) *ListNode {
    // base case
    if m == 1 {
        return reverseN(head, n)
    }
    // 前进到反转的起点触发 base case
    head.Next = reverseBetween(head.Next, m-1, n-1)
    return head
}

// 注意：javascript 代码由 chatGPT🤖 根据我的 java 代码翻译，旨在帮助不同背景的读者理解算法逻辑。
// 本代码不保证正确性，仅供参考。如有疑惑，可以参照我写的 java 代码对比查看。

var reverseBetween = function(head, m, n) {
    // base case
    if(m === 1) {
        // 反转以head开头的n个节点
        return reverseN(head, n);
    }
    // 将head.next作为起点反转前m-1个节点
    head.next = reverseBetween(head.next, m - 1, n - 1);
    return head;
}

至此，我们的最终大 BOSS 就被解决了。

四、最后总结

递归的思想相对迭代思想，稍微有点难以理解，处理的技巧是：不要跳进递归，而是利用明确的定义来实现算法逻辑。

处理看起来比较困难的问题，可以尝试化整为零，把一些简单的解法进行修改，解决困难的问题。

值得一提的是，递归操作链表并不高效。和迭代解法相比，虽然时间复杂度都是 O(N)，但是迭代解法的空间复杂度是 O(1)，而递归解法需要堆栈，空间复杂度是 O(N)。所以递归操作链表可以作为对递归算法的练习或者拿去和小伙伴装逼，但是考虑效率的话还是使用迭代算法更好。

最后，我在数据结构精品课中讲解了单链表的递归实现open in new window，应该能够让你进一步加深对递归的理解。

引用本文的文章

如何 K 个一组反转链表如何判断回文链表烧饼排序算法

引用本文的题目

安装我的 Chrome 刷题插件open in new window 点开下列题目可直接查看解题思路：

LeetCode	力扣
2. Add Two Numbersopen in new window	2. 两数相加open in new window
445. Add Two Numbers IIopen in new window	445. 两数相加 IIopen in new window
-	剑指 Offer 24. 反转链表open in new window
-	剑指 Offer II 024. 反转链表open in new window
-	剑指 Offer II 025. 链表中的两数相加open in new window

《labuladong 的算法小抄》已经出版，关注公众号查看详情；后台回复「全家桶」可下载配套 PDF 和刷题全家桶：

共同维护高质量学习环境，评论礼仪见这里，违者直接拉黑不解释

# 一、递归反转整个链表

# 二、反转链表前 N 个节点

# 三、反转链表的一部分

# 四、最后总结

一、递归反转整个链表

二、反转链表前 N 个节点

三、反转链表的一部分

四、最后总结