数据算法之反转链表(五种方法)

这篇具有很好参考价值的文章主要介绍了数据算法之反转链表(五种方法)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。


题目描述

给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
示例:
链表反转,数据算法,链表,算法,数据结构
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]

提示代码:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {

    }
}

这道题来自力扣的第206题,今天我们尝试使用五种不同的方法来实现链表的反转。

1.常规思路解题

第一种方法也是最容易想到的方法,就是将我们链表中的数据通过倒序存储到一个新的链表中即可完成链表的反转。

代码示例

//定义节点类
public class ListNode {
    int val;
    ListNode next;

    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }

    @Override
    //重写tostring方法,方便我们的节点按照题目要求输出
    public String toString() {
        //定义一个StringBuilder可变的字符串类,
        StringBuilder str = new StringBuilder(32);
        str.append("[");
        ListNode p = this;
        while (p != null) {
            str.append(p.val);
            if (p.next != null) {
                str.append(",");
            }
            p = p.next;

        }
        str.append("]");
        return str.toString();
    }
}

class Solution {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(5, null);
        ListNode listNode2 = new ListNode(4, listNode1);
        ListNode listNode3 = new ListNode(3, listNode2);
        ListNode listNode4 = new ListNode(2, listNode3);
        ListNode listNode5 = new ListNode(1, listNode4);
        System.out.println(listNode5.toString());
        System.out.println(reverseList(listNode5).toString());
    }

    public static ListNode reverseList(ListNode head) {
        ListNode newHead = new ListNode(head.val, null);
        ListNode p = head.next;
        while (p != null) {
            //头部的一个结点保存上一节点的最后一条数据
            //而后这段代码从这一节点开始,以后的数据都在头部插入,也就是这一节点之前去插入数据
            //为什么还是用原来的节点接收数据是因为他始终是一个头部的第一个节点,只不过不断的在更新头结点
            newHead = new ListNode(p.val, newHead);
            p = p.next;

        }
        return newHead;
    }
}

在以上的方法中只要理清了逻辑理解起来还是没问题的,建议先将基础常规思路看懂,再往下继续阅读。

2. 常规思路解题方法的优化

这种方法利用到了集合的概念,在Java中LinkList维护的就是这样一个节点类,在LinkList集合中有两个方法可以完成我们的操作分别为addFirst和removeFirst方法,在这里LinkList作为容器管理节点类,一个容器执行removeFirst删除头部节点类,另一个容器执行addFirs方法将那个容器里的数据添加到这个容器里,最后成功的实现反转链表。

在这里,我们呢先用Java提供的LinkList完成这一功能

代码示例

 LinkedList list = new LinkedList();
        LinkedList list2 = new LinkedList();
        Collections.addAll(list,1,2,3,4,5);
        System.out.println(list.toString());
        while (!list.isEmpty()){
            list2.addFirst(list.removeFirst());
        };
        System.out.println(list2.toString());
    }

在这里我们需要自己构建一个这样的容器,当然我们不要和java中的LinkList一样,只需要实现我们要使用的addFirst和removeFirst方法即可,c

代码示例

  public static ListNode reverseList2(ListNode head) {
        //定义两个容器
        //旧容器
        List list1 = new List(head);
        //新容器
        List list2 = new List(null);
        while (true){
            ListNode first = list1.removeFirst();
            if (first == null){//说明容器中没数据了
                break;
            }
            list2.addFirst(first);
        }
        return list2.head;
    }

}

//定义容器类
class List {
    //定义头结点指针
    ListNode head;

    public List(ListNode head) {
        this.head = head;
    }
    public void addFirst(ListNode listNode){
        //原来的头结点向后移动
        listNode.next = head;
        //新加入的节点成为头结点
         head = listNode ;
    }
    public ListNode removeFirst(){
        //先拿到头结点。
       ListNode firt = head;
       if (firt != null){
           //头结点删除,头结点之后的节点成为新的头结点
           head = firt.next;
        }
       return firt;

    };


}

3. 递归解题方法

先来看代码:

代码示例:

public static ListNode reverseList3(ListNode head) {
        //利用递归 实现链表的反转
        //递归跳出循环的条件,应该有两个
        //当 p.next == null表明是最后一个节点,
        // 另一个是P == null,这个时候说明传入时一个空节点,也要返回Null;
        // 两个条件同时满足即可结束递归。
        if (head == null || head.next == null){
            return head;//返回最后一个节点
        }
       //等所有递结束,开始归的时候调整我们的指针
        ListNode last = reverseList3(head.next);
        //递归思路:
        //只要让每次进来的节点反转他们的指向,即可完成反转链表
        //例如 传入的节点时 4 -> 5,现在使得5 -> 4 ,
        head.next.next = head;
        head.next = null;
        //接收最后一个节点

        return last;
    }

递归的方法思路就是通过反转节点的指针达到反转链表的效果,在上述代码中最难理解的是这么两段段代码,

        head.next.next = head;
        head.next = null;

在这里使用图的方式向大家解读这两段代码,

首先是head.next.next = head;

在没有递归之前,我们的链表状态是这样的:
链表反转,数据算法,链表,算法,数据结构
由于发生递归的代码在我们这一行代码的上面,也就是说只有找到了最后一个节点才会执行我们的这一段代码,也就是从4开始执行指针的反转。

如图所示:

链表反转,数据算法,链表,算法,数据结构
最终达到了反转链表的效果。

4. 指针思想解决问题

在这种方法中我们在同一条链表中操作,不同的是我们定义了三个指针来操作我们的节点中的指针使其完成反转链表的功能。

具体实现思路:

定义指针n1用来代表调整之后的链表的头结点。

定义指针o1用来代表未调整之前的链表头结点。

定义指针o2用来代表未调整之前的链表的第二个节点。

相关指针指向如图所示:

链表反转,数据算法,链表,算法,数据结构

通过不断的调整最终完成链表的反转,反转过程如下图所示:

链表反转,数据算法,链表,算法,数据结构
然后重复操作即可完成所有节点指针的调整。

代码示例:

    public static ListNode reverseList4(ListNode o1) {
        //头部指针在局部变量中被定义,
        //定义指针n1,因为节点还没有调整,所以n1和o1指向相同,即:
        ListNode n1 = o1;
        //定义指针o2,指向o1指向的下一个节点即:
        ListNode o2 = o1.next;

        //当o2指向为null时说明所有节点已经调整完毕,链表已经反转
        while (o2 != null){
            //让o1的指针指向o2的指针
            o1.next = o2.next;
            //02的指针指向n1.
            o2.next = n1;
            //更新n1指针
            n1 = o2;
            //更新o2的指针
            o2 = o1.next;

        }
        return n1;

    }

5. 指针方法另一种思路

这种方法和第二种方法是相似的,通过在一个链表中移除头节点添加到另一个链表的头部,不同的是对于第二种方法来说使用的是面向对象的思路来编写代码,在这种方法中则是使用的是面向过程的思路解决这一问题。

假设有两个链表

o1和n1是两个链表的头部节点。

o1代表的是我们旧的链表的头部节点,里面存储着我们要操作的原始数据。

n1代表着新链表,但是这个新的链表,在开始时是一个空的链表,通过不断的从旧的链表中的头部数据一个一个移除,再一个一个添加到新链表的头部,最终完成链表的反转。

一开始两个链表的状态如图:

链表反转,数据算法,链表,算法,数据结构

在完成一次搬移之后的两个链表的状态如下图所示:
链表反转,数据算法,链表,算法,数据结构
转化为代码为:

代码示例

public static ListNode reverseList4(ListNode o1) {
        //定义新链表头部节点:
        ListNode n1 = null;
        //当o1 = null的时候说明所有节点操作完成
        while (o1 != null){
            //将第二次循环o1 的值先取出来
            ListNode o2 = o1.next;
            //o1的指针不再指向之前的节点,而是加入新节点指向新节点的头结点
            o1.next = n1;
            //更新新链表的头结点指针n1
            n1 = o1;
            //更新旧节点的头结点
            o1 = o2;

        }
        return n1;
    }

如果你完全理解了第四种解法,那么这种方法对你来说简直牛刀小试。文章来源地址https://www.toymoban.com/news/detail-772114.html

到了这里,关于数据算法之反转链表(五种方法)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构】--单链表力扣面试题②反转链表

    目录 题目链接:反转链表   法一:直接反转法 法二:头插法 题目分析: 创建一个新链表,然后值是逆置的行吗?不行。因为题目要求的是在 原链表上逆置,改变原链表的指向,并不是值的拷贝后的逆转 。 那其实总共有三种方法 。 法一,直接原地翻转。法二,头插法。

    2024年02月06日
    浏览(38)
  • 【数据结构】链表OJ面试题(《删除定值、反转、返回中间结点、倒数第k节点、合并链表》)+解析)

    还不清楚链表的码喵们可以看看前篇关于链表的详解 既然已经懂得了链表该如何实现,那么现在就趁热打铁开始练习!这里给码喵们整理了相对不错的一些OJ题来练习  力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 思路:遍历整个表,访问每个表的值并且删除再将nex

    2024年02月22日
    浏览(51)
  • 第14章_集合与数据结构拓展练习(前序、中序、后序遍历,线性结构,单向链表构建,单向链表及其反转,字符串压缩)

    1、前序、中序、后序遍历 分析: 完全二叉树: 叶结点只能出现在最底层的两层,且最底层叶结点均处于次底层叶结点的左侧 2、线性结构 3、其它 4、单向链表构建 (1)定义一个单向链表SingleLinked类 包含私有的静态内部类Node 包含Object类型的data属性和Node类型的next属性 包含

    2024年01月23日
    浏览(50)
  • 【JavaScript数据结构与算法】字符串类(反转字符串中的单词)

    个人简介 👀 个人主页: 前端杂货铺 🙋‍♂️ 学习方向: 主攻前端方向,也会涉及到服务端(Node.js) 📃 个人状态: 在校大学生一枚,已拿多个前端 offer(秋招) 🚀 未来打算: 为中国的工业软件事业效力 n 年 🥇 推荐学习:🍍前端面试宝典 🍉Vue2 🍋Vue3 🍓Vue2/3项目

    2023年04月09日
    浏览(91)
  • 【数据结构与算法】链表

    对于顺序表存在一些缺陷: 中间/头部的插入删除,时间复杂度为O(N) 。头部插入需要挪动后面的元素 增容需要申请新空间,拷贝数据,释放旧空间。会有不小的消耗。 增容一般是呈2倍的增长,势必会有一定的空间浪费。例如当前容量为100,满了以后增容到200,我们再继续插

    2023年04月09日
    浏览(48)
  • 【算法与数据结构】链表

    链表是由一串节点串联在一起的,链表的每个节点存储两个信息:数据+下一个节点的地址 分清楚两个概念:什么是内存内部,什么是程序内部 内存内部: 信息存储在内存空间里的 程序内部: 通过什么信息,去操作结构 如果想操作链表的话,我们依靠的是程序内部的信息,

    2024年02月03日
    浏览(45)
  • 02-链表 (数据结构和算法)

    3.1 链表的基本概念 前面我们在学习顺序表时,线性表的顺序存储结构的特点是逻辑关系上相邻的两个数据元素在物理位置上也是相邻的。我们会发现虽然顺序表的查询很快,时间复杂度为O(1),但是增删的效率是比较低的,因为每一次增删操作都伴随着大量的数据元素移动。为

    2024年02月16日
    浏览(46)
  • Python数据结构与算法-数据结构(列表、栈、队列、链表)

    数据结构是指相互之间存在这一种或者多种关系的数据元素的集合和该集合中元素之间的关系组成。 简单来说,数据结构就是设计数据以何种方式组织并存储在计算机中。 比如:列表、集合与字典等都是一种数据结构。 N.Wirth:“程序=数据结构+算法” 数据结构按照其 逻辑结

    2024年02月08日
    浏览(59)
  • 【数据结构与算法】双向链表

    作者:旧梦拾遗186 专栏:数据结构成长日记   带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了。 现在我们来通

    2024年02月11日
    浏览(58)
  • 【数据结构和算法】奇偶链表

    Java基础合集 数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 其他系列文章导航 文章目录 前言 一、题目描述 二、题解 2.1 方法一:分离节点后合并 三、代码 3.1 方法一:分离节点后合并 四、复杂度分析 4.1 方法一:分离节点后合并 这是力扣的 328 题,难

    2024年01月20日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包