链表是一种常见的数据结构，广泛应用于各种算法和程序设计中。反转链表是一个经典的面试题，也是理解递归和链表操作的好例子。本文将详细介绍如何使用递归方法在Java中反转链表，并逐步解析其背后的原理。
链表介绍
链表由一系列节点组成，每个节点包含两个部分：
数据域：存储节点的值。
指针域：指向下一个节点的引用。
在Java中，链表节点一般用以下类表示：
public class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
递归介绍
递归是一种通过函数调用自身来解决问题的方法。它将复杂问题分解为更小的子问题，直到子问题可以直接解决为止。每次递归调用都会在栈中创建一个新的栈帧，保存当前状态。递归结束时，栈帧依次弹出，恢复到上一层调用。
递归的基本要素：
基线条件（Base Case）：递归终止的条件，防止无限递归。
递归条件（Recursive Case）：将问题分解为更小的子问题，并调用自身。
反转链表
反转链表通常由迭代和递归两种方法，迭代比较简单、直接。递归实现代码就比较简洁。
递归反转链表的基本思路是将当前节点的next指针指向前一个节点，然后递归地对下一个节点进行同样的操作。递归的核心思想是将问题分解为更小的子问题，直到达到基本情况（通常是链表末尾）。
我们分以下三种常用情况进行示例。
递归反转整个链表
实现代码如下：
/**
* 反转整个链表
*/
public class ReverseAll {
/**
* 递归实现
* @param head
* @return
*/
public static ListNode reverseRec(ListNode head) {
// 基本情况：链表为空或只有一个节点
if (head == null || head.next == null) {
return head;
}
// 递归反转剩余部分
ListNode last = reverseRec(head.next);
// 将当前节点的下一个节点的next指针指向当前节点
head.next.next = head;
// 将当前节点的next指针置为null
head.next = null;
return last;
}
/**
* 迭代实现
* @param head
* @return
*/
public static ListNode reverseIte(ListNode head) {
// 链表为空或只有一个节点,则返回该节点
if (head == null || head.next == null) {
return head;
}
ListNode pre = null;
ListNode cur = head;
// 遍历链表
while (cur != null) {
// 记录当前节点的下一个节点
ListNode next = cur.next;
// 反转当前节点的指针
cur.next = pre;
// 移动prev到当前节点
pre = cur;
// 移动curr到下一个节点
cur = next;
}
return pre;
}
public static void main(String[] args) {
ListNode head1 = new ListNode(1);
ListNode head2 = new ListNode(2);
ListNode head3 = new ListNode(3);
ListNode head4 = new ListNode(4);
head1.next = head2;
head2.next = head3;
head3.next = head4;
head4.next = null;
ListNode reverse = reverseRec(head1);
//ListNode reverse = reverseIte(head1);
while (reverse != null) {
System.out.println(reverse.val);
reverse = reverse.next;
}
}
}
其核心思想是递归找到链表的最后一个节点，利用递归结束栈帧依次弹出，恢复到上一层调用的特性，将链表从后一次将指针指向前一个元素，实现链表的反转。
反转链表前N个节点
实现反转链表的前N个节点，在上一个实现的基础上将基线条件变为 n==1,同时需要记录后驱节点successor，并将原来head的后驱节点设置为successor;
实现代码如下：
/**
* 反转链表的前N个节点
*/
public class ReverseFront {
/**
* 递归实现
* @param head
* @return
*/
//记录不需要反转的头节点
public static ListNode successor=null;
public static ListNode reverseRec(ListNode head,int n) {
// 记录后半部分的起始节点，并返回新的头节点
if (n == 1) {
successor = head.next;
return head;
}
// 以head.next为起点，反转前n-1个节点(每多一次递归，则反转的节点少一个)
ListNode last = reverseRec(head.next,n-1);
// 将当前节点的下一个节点的next指针指向当前节点
head.next.next = head;
// 将当前节点的next指针置为后驱节点
head.next = successor;
return last;
}
/**
* 迭代实现
* @param head
* @return
*/
public static ListNode reverseIte(ListNode head,int n) {
// 链表为空或只有一个节点,则返回该节点
if (head == null || head.next == null) {
return head;
}
ListNode pre = null;
ListNode cur = head;
ListNode successor=null;
int i = 1;
// 遍历链表
while (i <= n) {
// 记录当前节点的下一个节点
ListNode next = cur.next;
// 反转当前节点的指针
cur.next = pre;
// 移动prev到当前节点
pre = cur;
// 移动curr到下一个节点
cur = next;
//记录后半部分的其实节点
successor = next;
i++;
}
//将反转之后的前半部分链表的next指针指向后半部分链表
head.next = successor;
return pre;
}
public static void main(String[] args) {
ListNode head1 = new ListNode(1);
ListNode head2 = new ListNode(2);
ListNode head3 = new ListNode(3);
ListNode head4 = new ListNode(4);
head1.next = head2;
head2.next = head3;
head3.next = head4;
head4.next = null;
ListNode reverse = reverseRec(head1,2);
//ListNode reverse = reverseIte(head1,2);
while (reverse != null) {
System.out.println(reverse.val);
reverse = reverse.next;
}
}
}
反转链表区间[m,n]中的元素
/**
* 反转链表区间[m,n]中的元素
*/
public class ReverseSection {
/**
* 递归实现
* @param head
* @return
*/
//记录不需要反转的头节点
public static ListNode successor=null;
public static ListNode reverseRecN(ListNode head,int n) {
// 记录后半部分的起始节点，并返回新的头节点
if (n == 1) {
successor = head.next;
return head;
}
// 以head.next为起点，反转前n-1个节点(每多一次递归，则反转的节点少一个)
ListNode last = reverseRecN(head.next,n-1);
// 将当前节点的下一个节点的next指针指向当前节点
head.next.next = head;
// 将当前节点的next指针置为后驱节点
head.next = successor;
return last;
}
/**
* 递归实现
* @param head
* @return
*/
public static ListNode reverseRec(ListNode head,int m,int n) {
//m如果==1，则说明需要反转前n个节点
if(m == 1){
return reverseRecN(head,n);
}
// 前进到反转的起点触发基线线条件
head.next = reverseRec(head.next,m-1,n-1);
return head;
}
/**
* 迭代实现
* @param head
* @return
*/
public static ListNode reverseIte(ListNode head,int m,int n) {
// 链表为空或只有一个节点,则返回该节点
if (head == null || head.next == null) {
return head;
}
ListNode pre = null;
ListNode cur = head;
ListNode nodem1=null;
ListNode nodem=null;
int i = 1;
// 遍历链表
while (i <= n ) {
// 记录当前节点的下一个节点
ListNode next = cur.next;
//记录m-1位置的节点
if(i == m-1){
nodem1=cur;
}
//记录m位置的节点
if(i == m){
nodem=cur;
}
//反转区间中的元素
if(i>=m){
// 反转当前节点的指针
cur.next = pre;
}
// 移动prev到当前节点
pre = cur;
// 移动curr到下一个节点
cur = next;
if(i == n){
//将反转区间的第一个元素的指针指向后半部分链表
nodem.next = next;
//将半部分链表的指针指向反转区间的最后一个元素
nodem1.next = pre;
}
i++;
}
return head;
}
public static void main(String[] args) {
ListNode head1 = new ListNode(1);
ListNode head2 = new ListNode(2);
ListNode head3 = new ListNode(3);
ListNode head4 = new ListNode(4);
head1.next = head2;
head2.next = head3;
head3.next = head4;
head4.next = null;
ListNode reverse = reverseRec(head1,2,4);
//ListNode reverse = reverseIte(head1,2,4);
while (reverse != null) {
System.out.println(reverse.val);
reverse = reverse.next;
}
}
}
复杂度分析
- 时间复杂度
不管时递归还是迭代，都只需要循环或者迭代n次就可以完成反转，所以时间复杂度都是O(n),
- 空间复杂度
迭代解法的空间复杂度是O(1),而递归需要堆栈，空间复杂度是O(n);
- 选择建议
如果链表较短且代码简洁性更重要，可以选择递归方法。
如果链表较长或需要优化空间效率，优先选择迭代方法。
总结
递归反转链表是一个经典的算法问题，通过递归方法可以简洁地实现链表的反转。理解递归的关键在于将问题分解为更小的子问题，并正确处理基本情况。希望本文能帮助你更好地理解递归和链表操作，并在实际编程中灵活运用。
