单链表的花式反转方法汇总

labuladong原创约 4232 字

本文讲解的例题

LeetCode	力扣	难度
206. Reverse Linked List	206. 反转链表	🟢
92. Reverse Linked List II	92. 反转链表 II	🟠
25. Reverse Nodes in k-Group	25. K 个一组翻转链表	🔴

反转单链表的迭代解法不是一个困难的事情，但是递归实现就有点难度了。如果再加一点难度，让你仅仅反转单链表中的一部分，你是否能够同时用迭代和递归实现呢？再进一步，如果让你 k 个一组反转链表，阁下又应如何应对？

本文就来由浅入深，一次性解决这些链表操作的问题。我会同时使用递归和迭代的方式，并结合可视化面板帮助你理解，以此强化你的递归思维以及操作链表指针的能力。

反转整个单链表

在力扣/LeetCode 中，单链表的通用结构是这样的：

java 🟢

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

cpp 🤖

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

python 🤖

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

go 🤖

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

javascript 🤖

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

单链表反转是一个比较基础的算法题，力扣第 206 题「反转链表」就是这个问题：

下面我们来尝试用多种方法解决这个问题。

迭代解法

这道题的常规做法就是迭代解法，通过操作几个指针，将链表中的每个节点的指针方向反转，没什么难点，主要是指针操作的细节问题。

这里直接给出代码，结合注释和可视化面板应该不难理解：

java 🟢

class Solution {
    // 反转以 head 为起点的单链表
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 由于单链表的结构，至少要用三个指针才能完成迭代反转
        // cur 是当前遍历的节点，pre 是 cur 的前驱结点，nxt 是 cur 的后继结点
        ListNode pre, cur, nxt;
        pre = null; cur = head; nxt = head.next;
        while (cur != null) {
            // 逐个结点反转
            cur.next = pre;
            // 更新指针位置
            pre = cur;
            cur = nxt;
            if (nxt != null) {
                nxt = nxt.next;
            }
        }
        // 返回反转后的头结点
        return pre;
    }
}

cpp 🤖

class Solution {
public:
    // 反转以 head 为起点的单链表
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        // 由于单链表的结构，至少要用三个指针才能完成迭代反转
        // cur 是当前遍历的节点，pre 是 cur 的前驱结点，nxt 是 cur 的后继结点
        ListNode *pre, *cur, *nxt;
        pre = nullptr; cur = head; nxt = head->next;
        while (cur != nullptr) {
            // 逐个结点反转
            cur->next = pre;
            // 更新指针位置
            pre = cur;
            cur = nxt;
            if (nxt != nullptr) {
                nxt = nxt->next;
            }
        }
        // 返回反转后的头结点
        return pre;
    }
};

python 🤖

class Solution:
    # 反转以 head 为起点的单链表
    def reverseList(self, head: ListNode) -> ListNode:
        if head is None or head.next is None:
            return head
        # 由于单链表的结构，至少要用三个指针才能完成迭代反转
        # cur 是当前遍历的节点，pre 是 cur 的前驱结点，nxt 是 cur 的后继结点
        pre, cur, nxt = None, head, head.next
        while cur is not None:
            # 逐个结点反转
            cur.next = pre
            # 更新指针位置
            pre = cur
            cur = nxt
            if nxt is not None:
                nxt = nxt.next
        # 返回反转后的头结点
        return pre

go 🤖

// 反转以 head 为起点的单链表

func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    // 由于单链表的结构，至少要用三个指针才能完成迭代反转
    // cur 是当前遍历的节点，pre 是 cur 的前驱结点，nxt 是 cur 的后继结点
    var pre, cur, nxt *ListNode
    pre, cur, nxt = nil, head, head.Next
    for cur != nil {
        // 逐个结点反转
        cur.Next = pre
        // 更新指针位置
        pre = cur
        cur = nxt
        if nxt != nil {
            nxt = nxt.Next
        }
    }
    // 返回反转后的头结点
    return pre
}

javascript 🤖

var reverseList = function(head) {
    if (head == null || head.next == null) {
        return head;
    }
    // 由于单链表的结构，至少要用三个指针才能完成迭代反转
    // cur 是当前遍历的节点，pre 是 cur 的前驱结点，nxt 是 cur 的后继结点
    var pre, cur, nxt;
    pre = null; cur = head; nxt = head.next;
    while (cur != null) {
        // 逐个结点反转
        cur.next = pre;
        // 更新指针位置
        pre = cur;
        cur = nxt;
        if (nxt != null) {
            nxt = nxt.next;
        }
    }
    // 返回反转后的头结点
    return pre;
}

操作指针的小技巧

上面操作单链表的代码逻辑不复杂，而且也不止我这一种正确的写法。但是操作指针的时候，有一些很基本、很简单的小技巧，可以让你写代码的思路更清晰：

1、一旦出现类似 nxt.next 这种操作，就要条件反射地想到，先判断 nxt 是否为 null，否则容易出现空指针异常。

2、注意循环的终止条件。你要知道循环终止时，各个指针的位置，这样才能保返回正确的答案。如果你觉得有点复杂想不清楚，那就动手画一个最简单的场景跑一下算法，比如这道题就可以画一个只有两个节点的单链表 1->2，然后就能确定循环终止后各个指针的位置了。

递归解法

上面的迭代解法操作指针虽然有些繁琐，但是思路还是比较清晰的。如果现在让你用递归来反转单链表，你有啥想法没？

对于初学者来说可能很难想到，这很正常。如果你学习了后文的二叉树系列算法思维，回头再来看这道题，才有可能自己想出这个算法。

因为二叉树结构本身就是单链表的延伸，相当于是二叉链表嘛，所以二叉树上的递归思维，套用到单链表上是一样的。

递归反转单链表的关键在于，这个问题本身是存在子问题结构的。

比方说，现在给你输入一个以 1 为头结点单链表 1->2->3->4，那么如果我忽略这个头结点 1，只拿出 2->3->4 这个子链表，它也是个单链表对吧？

那么你这个 reverseList 函数，只要输入一个单链表，就能给我反转对吧？那么你能不能用这个函数先来反转 2->3->4 这个子链表呢，然后再想办法把 1 接到反转后的 4->3->2 的最后面，是不是就完成了整个链表的反转？

reverseList(1->2->3->4) = reverseList(2->3->4) -> 1

这就是「分解问题」的思路，通过递归函数的定义，把原问题分解成若干规模更小、结构相同的子问题，最后通过子问题的答案组装原问题的解。

在后面的教程中会有专门的章节讲解和练习这种思维，这里不展开。

先来看看递归反转单链表的代码实现：

java 🟢

class Solution {
    // 定义：输入一个单链表头结点，将该链表反转，返回新的头结点
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode last = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return last;
    }
}

cpp 🤖

class Solution {
public:
    // 定义：输入一个单链表头结点，将该链表反转，返回新的头结点
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* last = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return last;
    }
};

python 🤖

class Solution:
    # 定义：输入一个单链表头结点，将该链表反转，返回新的头结点
    def reverseList(self, head):
        if head is None or head.next is None:
            return head
        last = self.reverseList(head.next) 
        head.next.next = head 
        head.next = None
        return last

go 🤖

// 定义：输入一个单链表头结点，将该链表反转，返回新的头结点
func reverseList(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	last := reverseList(head.Next)
	head.Next.Next = head
	head.Next = nil
	return last
}

javascript 🤖

var reverseList = function(head) {
    // 定义：输入一个单链表头结点，将该链表反转，返回新的头结点
    if (head == null || head.next == null) {
        return head;
    }
    var last = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return last;
}

这个算法常常拿来显示递归的巧妙和优美，我们下面来详细解释一下这段代码，最后在给出可视化面板，你可以自己动手探究一下递归过程。

对于「分解问题」思路的递归算法，最重要的就是明确递归函数的定义。具体来说，我们的 reverseList 函数定义是这样的：

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

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

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

ListNode last = reverseList(head.next);

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

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

并且根据函数定义，reverseList 函数会返回反转之后的头结点，我们用变量 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;

这样，整个单链表就完成反转了，神不神奇？下面是递归反转链表的可视化过程：

不建议陷入递归细节

虽然可视化面板可以展示整个递归过程的所有细节，但我不建议初学者过于执着于细节。建议先依照上面图示讲解的思维方式理解递归，然后再通过可视化面板加深理解。

递归操作链表的效率不如迭代

值得一提的是，递归操作链表并不高效。

递归解法和迭代解法相比，时间复杂度都是 O(N)，但是迭代解法的空间复杂度是 O(1)，而递归解法需要堆栈，空间复杂度是 O(N)。

所以递归操作链表可以用来练习递归思维，但是考虑效率的话还是使用迭代算法更好。

反转链表前 N 个节点

这次我们实现一个这样的函数：

java 🟢

// 将链表的前 n 个节点反转（n <= 链表长度）
ListNode reverseN(ListNode head, int n)

cpp 🤖

// 将链表的前 n 个节点反转（n <= 链表长度）
ListNode* reverseN(ListNode* head, int n);

python 🤖

# 将链表的前 n 个节点反转（n <= 链表长度）
def reverseN(head: ListNode, n: int):

go 🤖

// 将链表的前 n 个节点反转（n <= 链表长度）
func ReverseN(head *ListNode, n int) *ListNode {}

javascript 🤖

// 将链表的前 n 个节点反转（n <= 链表长度）
var reverseN = function(head, n) {}

比如说对于下图链表，执行 reverseN(head, 3)：

单链表的花式反转方法汇总

206. 反转链表 https://leetcode.cn/problems/reverse-linked-list

206. Reverse Linked List https://leetcode.com/problems/reverse-linked-list

25. K 个一组翻转链表 https://leetcode.cn/problems/reverse-nodes-in-k-group

25. Reverse Nodes in k-Group https://leetcode.com/problems/reverse-nodes-in-k-group

92. 反转链表 II https://leetcode.cn/problems/reverse-linked-list-ii

92. Reverse Linked List II https://leetcode.com/problems/reverse-linked-list-ii

反转整个单链表

迭代解法

递归解法

反转链表前 N 个节点

迭代解法

递归解法

反转链表的一部分

迭代解法

递归解法

K 个一组反转链表

思路分析

代码实现

最后总结