当前位置： 首页 > article >正文

算法系列之递归反转单链表

article 2025/2/28 1:35:15

_20250225223348.jpg

链表是一种常见的数据结构，广泛应用于各种算法和程序设计中。反转链表是一个经典的面试题，也是理解递归和链表操作的好例子。本文将详细介绍如何使用递归方法在Java中反转链表，并逐步解析其背后的原理。

链表介绍

链表由一系列节点组成，每个节点包含两个部分：

  1. 数据域：存储节点的值。

  2. 指针域：指向下一个节点的引用。

在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);

  • 选择建议

如果链表较短且代码简洁性更重要，可以选择递归方法。

如果链表较长或需要优化空间效率，优先选择迭代方法。

总结

递归反转链表是一个经典的算法问题，通过递归方法可以简洁地实现链表的反转。理解递归的关键在于将问题分解为更小的子问题，并正确处理基本情况。希望本文能帮助你更好地理解递归和链表操作，并在实际编程中灵活运用。


http://www.kler.cn/a/563890.html

相关文章：

  • 四款 AI 协作办公工具，AI工具库革新办公效率
  • 2025年软考报名费用是多少?全国费用汇总!
  • Hive从入门到运用
  • win11本地部署deepseek大模型（安装ollama+docker+open-webui）最终实现自己的项目可通过API调用投喂数据后的模型
  • 关于order by的sql注入实验
  • 若依框架集成阿里云OSS
  • ElasticSearch13-8.x操作
  • MySQL（面试题 - 同类型归纳面试题）
  • Linux 常用命令大全及详解
  • 性能测试丨微信小程序性能优化指南
  • DeepSeek掘金——蒸馏DeepSeek-R1到自己的模型
  • VMware虚拟机Mac版安装Win10系统
  • 仿12306购票系统（3）
  • CF 90A.Cableway(Java实现)
  • python接入串口数据
  • 地理数据可视化：飞线说明（笔记）
  • 【MATLAB中的图像数据结构】
  • 企业知识库搭建：14款开源与免费系统选择
  • 电商项目-秒杀系统(一)秒杀业务分析
  • MySQL——创建与管理视图