单链表的花式反转方法汇总
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | Difficulty |
|---|---|
| 206. Reverse Linked List | 🟢 |
| 25. Reverse Nodes in k-Group | 🔴 |
| 92. Reverse Linked List II | 🟠 |
Reversing a singly linked list using an iterative approach is not difficult, but the recursive implementation can be a bit challenging. If we add another layer of complexity by asking you to reverse only a part of the singly linked list, can you achieve this using both iterative and recursive methods? Furthermore, if you were asked to reverse the list in groups of k nodes, how would you handle it?
This article will delve from the basics to the advanced, tackling these linked list manipulation problems all at once. I will use both recursive and iterative approaches, and combine them with visual aids to help you understand, thereby strengthening your recursive thinking and your ability to manipulate linked list pointers.
Reversing the Entire Singly Linked List
In platforms like LeetCode, the general structure of a singly linked list is as follows:
// Structure of a single linked list node
class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}// Structure of a single linked list node
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};# Structure of a singly linked list node
class ListNode:
def __init__(self, x):
self.val = x
self.next = None// Structure of a singly linked list node
type ListNode struct {
val int
next *ListNode
}// Structure of a singly linked list node
var ListNode = function(x) {
this.val = x;
this.next = null;
}Reversing a singly linked list is a basic algorithm problem. LeetCode's problem #206, "Reverse Linked List," addresses this issue:
206. Reverse Linked List | 力扣 | LeetCode |
Given the head of a singly linked list, reverse the list, and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5] Output: [5,4,3,2,1]
Example 2:
Input: head = [1,2] Output: [2,1]
Example 3:
Input: head = [] Output: []
Constraints:
- The number of nodes in the list is the range
[0, 5000]. -5000 <= Node.val <= 5000
Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?
Let's try solving this problem using multiple methods.
Iterative Solution
The standard approach to this problem is the iterative method. It involves manipulating several pointers to reverse the direction of each node in the list. There are no major difficulties, just details related to pointer operations.
Here is the code directly. With the help of comments and the visualization panel, it should be easy to understand:
class Solution {
// Reverse the linked list starting from head
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
// Due to the structure of a singly linked list, at least three pointers are needed to complete the iterative reversal
// cur is the current node being traversed, pre is the predecessor node of cur, nxt is the successor node of cur
ListNode pre, cur, nxt;
pre = null; cur = head; nxt = head.next;
while (cur != null) {
// Reverse each node
cur.next = pre;
// Update pointer positions
pre = cur;
cur = nxt;
if (nxt != null) {
nxt = nxt.next;
}
}
// Return the head node after reversal
return pre;
}
}class Solution {
public:
// Reverse the singly linked list starting from head
ListNode* reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
// Due to the structure of a singly linked list, at least three pointers are needed to complete the iterative reversal
// cur is the current node being traversed, pre is the predecessor node of cur, nxt is the successor node of cur
ListNode *pre, *cur, *nxt;
pre = nullptr; cur = head; nxt = head->next;
while (cur != nullptr) {
// Reverse each node
cur->next = pre;
// Update pointer positions
pre = cur;
cur = nxt;
if (nxt != nullptr) {
nxt = nxt->next;
}
}
// Return the head node after reversal
return pre;
}
};class Solution:
# Reverse the linked list starting from head
def reverseList(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
# Due to the structure of a singly linked list, at least three pointers are needed to complete the iterative reversal
# cur is the current node being traversed, pre is the predecessor node of cur, nxt is the successor node of cur
pre, cur, nxt = None, head, head.next
while cur is not None:
# Reverse each node
cur.next = pre
# Update pointer positions
pre = cur
cur = nxt
if nxt is not None:
nxt = nxt.next
# Return the head node after reversal
return pre// Reverse a singly linked list starting from head
func reverseList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
// Due to the structure of a singly linked list, at least three pointers are needed to complete the iterative reversal
// cur is the current node being traversed, pre is the predecessor node of cur, and nxt is the successor node of cur
var pre, cur, nxt *ListNode
pre, cur, nxt = nil, head, head.Next
for cur != nil {
// Reverse each node
cur.Next = pre
// Update pointer positions
pre = cur
cur = nxt
if nxt != nil {
nxt = nxt.Next
}
}
// Return the head node of the reversed list
return pre
}var reverseList = function(head) {
if (head == null || head.next == null) {
return head;
}
// Due to the structure of a singly linked list, at least three pointers are needed to complete the iterative reversal
// cur is the current node being traversed, pre is the predecessor node of cur, and nxt is the successor node of cur
var pre, cur, nxt;
pre = null; cur = head; nxt = head.next;
while (cur != null) {
// Reverse each node
cur.next = pre;
// Update pointer positions
pre = cur;
cur = nxt;
if (nxt != null) {
nxt = nxt.next;
}
}
// Return the head node after reversal
return pre;
}Tips for Pointer Manipulation
The code for manipulating a singly linked list above is not complex, and there are multiple correct ways to write it. However, when dealing with pointers, there are some basic and simple tips that can make your coding process clearer:
Whenever you see operations like
nxt.next, you should instinctively think to check ifnxtis null first to avoid null pointer exceptions.Pay attention to the termination conditions of loops. You need to know the positions of each pointer when the loop ends to ensure you return the correct result. If you find it a bit complex and unclear, try drawing a simple scenario and running the algorithm, such as a singly linked list with only two nodes
1->2. This will help you determine the positions of each pointer after the loop terminates.
Recursive Solution
While the iterative solution above involves some cumbersome pointer manipulation, the logic is relatively clear. How would you feel about using recursion to reverse a singly linked list?
It might be challenging for beginners to come up with this idea, and that's normal. If you study the binary tree series algorithms discussed later, you might be able to figure out this algorithm when you revisit this problem.
Since the binary tree structure is an extension of the singly linked list, essentially a binary linked list, the recursive thinking applied to binary trees can be similarly applied to singly linked lists.
The key to recursively reversing a singly linked list lies in the fact that the problem itself has a subproblem structure.
For example, if you are given a singly linked list starting with node 1 as 1->2->3->4, and you ignore the head node 1, taking only the sub-list 2->3->4, it is still a singly linked list, right?
Your reverseList function can reverse any singly linked list you input, correct? So, can you use this function to first reverse the sub-list 2->3->4, and then find a way to attach 1 to the end of the reversed list 4->3->2? Wouldn't that complete the reversal of the entire list?
reverseList(1->2->3->4) = reverseList(2->3->4) -> 1This is the idea of "problem decomposition." By defining a recursive function, we break down the original problem into several smaller subproblems with the same structure. Finally, we assemble the solution to the original problem from the solutions to these subproblems.
There will be a dedicated chapter in the following tutorials to explain and practice this way of thinking, so we won't elaborate on it here.
Let's first look at the code implementation for recursively reversing a singly linked list:
class Solution {
// Definition: Input the head node of a singly linked list, reverse the list, and return the new head node
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;
}
}class Solution {
public:
// Definition: Input a head node of a singly linked list, reverse the list, and return the new head node
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;
}
};class Solution:
# Definition: Input a head node of a singly linked list, reverse the list, and return the new head node
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// Definition: Input the head node of a singly linked list, reverse the list, and return the new head node
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
}var reverseList = function(head) {
// Definition: Input a head node of a singly linked list, reverse the list, and return the new head node
if (head == null || head.next == null) {
return head;
}
var last = reverseList(head.next);
head.next.next = head;
head.next = null;
return last;
}This algorithm is often used to demonstrate the elegance and cleverness of recursion. Let's dive into explaining this code in detail, and at the end, we'll provide a visualization panel where you can explore the recursive process yourself.
For recursive algorithms that follow the "divide and conquer" approach, the most crucial part is to clearly define the recursive function. Specifically, our reverseList function is defined as follows:
Given a node head, reverse the linked list starting from head, and return the new head of the reversed list.
Once you understand the function's definition, let's look at the problem. For example, suppose we want to reverse this linked list:
When we call reverseList(head), the recursion will occur at this point:
ListNode last = reverseList(head.next);Don't jump into recursion (how many stacks can your brain handle?), but instead, based on the function definition we just discussed, figure out what this code will produce:
After executing reverseList(head.next), the entire linked list will look like this:
And according to the function definition, the reverseList function will return the head of the reversed list, which we store in the variable last.
Now let's look at the following code:
head.next.next = head;Next:
head.next = null;
return last;Isn't it amazing? This way, the entire linked list is reversed! Recursive code is so concise and elegant, but there are two points to pay attention to:
- The recursive function needs a base case, which is this line:
if (head == null || head.next == null) {
return head;
}This means that if the linked list is empty or has only one node, the reversal result is itself, and you can return it directly.
- After the linked list is reversed recursively, the new head node is
last, and the previousheadbecomes the last node. Don't forget to set the end of the list to point to null:
head.next = null;With this, the entire singly linked list is reversed. Amazing, isn't it? Below is the visualization process of reversing a linked list recursively:
Not Recommended to Get Stuck in Recursive Details
Although the visualization panel can show all the details of the recursive process, I don't recommend beginners to get too caught up in the details. It's better to first understand according to the framework thinking of Essence of Data Structures and Algorithms, and then deepen your understanding through the visualization panel.
Recursive Operations on Linked Lists Are Less Efficient Than Iterative
It's worth mentioning that recursive operations on linked lists are not efficient.
Compared to iterative solutions, both have a time complexity of O(N), but the iterative solution has a space complexity of O(1), while the recursive solution requires a stack, making its space complexity O(N).
So, using recursion for linked list operations can be a good practice for recursive algorithms or to impress your friends, but for efficiency, iterative algorithms are better.
Reverse the First N Nodes of a Linked List
This time, we will implement a function like this:
// Reverse the first n nodes of the linked list (n <= length of the list)
ListNode reverseN(ListNode head, int n)// Reverse the first n nodes of the linked list (n <= length of the list)
ListNode* reverseN(ListNode* head, int n);# Reverse the first n nodes of the linked list (n <= length of the list)
def reverseN(head: ListNode, n: int):// Reverse the first n nodes of the linked list (n <= length of the list)
func ReverseN(head *ListNode, n int) *ListNode {}// Reverse the first n nodes of the linked list (n <= length of the linked list)
var reverseN = function(head, n) {}For example, for the linked list shown below, execute reverseN(head, 3):
