【算法手记03】反转链表

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

反转链表很重要,是链表题中的高频考点,部分题目可能还需要将反转链表抽出来作为一个函数使用。这几种方式都必须熟练手搓。

反转整个链表

lc206.给定单链表头结点,给出反转后的链表。

使用dummy虚拟头结点实现

反转后的新链表带一个dummy结点,将原链表的结点依次插入dummy结点之后,即可完成反转。过程大致如下:
【算法手记03】反转链表,算法,链表,数据结构
【算法手记03】反转链表,算法,链表,数据结构

下图中,cur作为遍历链表的指针,next指向cur的下一个节点。
【算法手记03】反转链表,算法,链表,数据结构

以第一个结点为例,cur结点尾插dummy节点同样遵守"先接管后继,再接入前驱"的准则,先令cur.next指向dummy.next,也就是null;随后令dummy.next指向cur,插入完成。

从上图可以看到,在进行插入之前,我们令cur的后一个结点为next节点,这就便于我们在将前一个节点插入完成后,令cur指针指向next指针。
【算法手记03】反转链表,算法,链表,数据结构
最后,考虑边界。
由于引入了dummy节点,因此头节点不需要特殊处理。现在需要考虑循环跳出的条件,即什么时候反转完了。

当cur指针指向最后一个节点,next指针指向null。cur节点插入新链表后,新的cur指针指向原来next指针,也就是null,此时退出循环。也就是循环进入条件应该是cur!=null.
【算法手记03】反转链表,算法,链表,数据结构

public ListNode reverseList(ListNode head) {  
    ListNode cur = head;  
    ListNode dummy = new ListNode();  
    while (cur!=null){  
        ListNode next = cur.next;  
        //先接管后继  
        cur.next = dummy.next;  
        //再接入前驱  
        dummy.next = cur;  
        cur = next;  
    }  
    return dummy.next;  
}

直接操作原链表实现

此方法不引入新链表,空间复杂度更低,但也更复杂。
先画出初始和结束的状态:
【算法手记03】反转链表,算法,链表,数据结构

下图中,cur作为遍历链表指针,同上。
随后,cur的next指向它的前一个结点prev。初始时,prev为null。随后,prev、cur依次向后移1位。
【算法手记03】反转链表,算法,链表,数据结构
当cur指向null时,prev指向链表末尾,此时反转完毕,循环跳出。
【算法手记03】反转链表,算法,链表,数据结构
代码如下:

ListNode prev = null;  
ListNode cur = head;  
while (cur!=null){  
    ListNode next = cur.next;  
    cur.next = prev;  
    prev = cur;  
    cur = next;  
}  
return prev;

指定区间反转

lc92
【算法手记03】反转链表,算法,链表,数据结构
【算法手记03】反转链表,算法,链表,数据结构

本题与lc206反转整个链表的实现方法是类似的。
lc206中,我们将遍历到的原链表的结点依次插到dummy结点的后面,那么本题我们只需要将遍历到的区间节点依次插入到反转区间的第一个位置,也就是反转区间的前驱结点之后即可。

本题指针较多,写题的时候一定要画图,不然很容易把自己搞乱。

过程如下:
【算法手记03】反转链表,算法,链表,数据结构

下面来考虑具体细节。我们选取反转区间中间的一部分来讨论实现细节。
如下图。由上面可以知道,cur指针每往前走一步,都要把自身插到pre结点之后。
类似这种更换链表中指定结点的位置的需求,我们一定要确定好结点的前驱和后继,以便它变换位置后,其他顺序不变。
【算法手记03】反转链表,算法,链表,数据结构
明白这点之后,开始操作,将cur插入pre之后。

  1. 插入结点操作遵循 “先接管后继,再接入前驱” 原则,cur先将其next指针指向pre的next,随后pre的next指针指向cur。
  2. front的next指针指向next,cur指针移向next,大功告成。
    【算法手记03】反转链表,算法,链表,数据结构
    【算法手记03】反转链表,算法,链表,数据结构

随后考虑初始化条件。front最开始应该和cur同时指向pre.next。
这是因为,按照上面的方法,第一个节点cur.next指向pre.next时,出现自环。
front指向next时,链表恢复正常。由此可见front最开始应该和cur指向同一个位置。第二次移动之后,cur都会移向next,而front不会变。
实际上,front指针永远指向原区间的第一个结点。
【算法手记03】反转链表,算法,链表,数据结构
【算法手记03】反转链表,算法,链表,数据结构

再考虑边界条件。

  1. 由题中所给的变量范围可知,链表至少会有一个结点、left一定不会大于right,因此非法输入不需要考虑。
  2. 考虑指针越界。当right=n也就是区间到链表末尾时,当cur移动到right处,其next为null,不会触发空指针异常。
    综上,本题不需要额外考虑边界条件。

想好后,代码就很好写了。

public ListNode reverseBetween(ListNode head, int left, int right) {  
    ListNode dummy = new ListNode();  
    dummy.next = head;  
    int cnt = 1;  
    ListNode pre = dummy,cur,front;  
    while (cnt<left){  
        cnt++;  
        pre = pre.next;  
    }  
    cur = pre.next;  
    front = cur;  
  
    while (cnt<=right){  
        ListNode next = cur.next;  
        cur.next = pre.next;  
        pre.next = cur;  
        front.next = next;  
        cur = next;  
        cnt++;  
    }  
    return dummy.next;  
  
}

K个一组反转(hard)

lc25.
给你链表的头节点 head ,每 k 个节点一组进行翻转,请你返回修改后的链表。
k 是一个正整数,它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

【算法手记03】反转链表,算法,链表,数据结构
提示:

  • 链表中的节点数目为 n
  • 1 <= k <= n <= 5000
  • 0 <= Node.val <= 1000

思路与指定区间反转类似。需要注意以下几个点:

  1. 使用for循环而不是while循环会更好
  2. 需要先计算出要反转几个区间。
  3. 区间反转完毕后,新的pre、front、cur指针指向一定要弄清楚。

针对第二点,我们可以先画出k=2时,第一个区间已经反转完毕各指针的指向情况。
【算法手记03】反转链表,算法,链表,数据结构
当开始反转第二个区间时,各指针指向应该变成下面这样:
可以得出结论。当一个区间反转完毕时,需要移动pre、front指针,而cur指针无需移动。
【算法手记03】反转链表,算法,链表,数据结构
代码如下:

public ListNode reverseKGroup(ListNode head, int k) {  
    ListNode dummy = new ListNode();  
    dummy.next = head;  
    ListNode cur = head;  
    int len = 0;  
    while (cur!=null){  
        len++;  
        cur = cur.next;  
    }  
    int groupCnt = len/k;  
    ListNode pre = dummy;  
    cur = pre.next;  
    ListNode front = pre.next;  
    for(int i = 0;i < groupCnt;i++){  
        for(int j = 0;j < k;j++) {  
            ListNode next = cur.next;  
            cur.next = pre.next;  
            pre.next = cur;  
            front.next = next;  
            cur = next;  
        }  
        pre = front;  
        front = cur;  
    }  
    return dummy.next;  
  
}

两两交换链表节点

lc24.【算法手记03】反转链表,算法,链表,数据结构
如下图所示,遍历指针cur应在交换节点区间前一位,方便我们将cur后面的第二个节点插入到cur之后,随后node1指向next,cur移动到node1的位置。
【算法手记03】反转链表,算法,链表,数据结构

考虑边界条件。这里会出现node1、node2、next,其中node1、2都必须非空,因为它们要进行交换。next空不空就无所谓了。
整体而言思路还是比较简单的,代码如下:

public ListNode swapPairs(ListNode head) {  
    ListNode dummy = new ListNode();  
    dummy.next = head;  
    ListNode cur = dummy;  
    while (cur.next!=null && cur.next.next!=null){  
        ListNode node1 = cur.next;  
        ListNode node2 = node1.next;  
        ListNode next = node2.next;  
        node2.next = node1;  
        cur.next = node2;  
        node1.next = next;  
        cur = node1;  
    }  
    return dummy.next;   
}

链表加法

lc445
【算法手记03】反转链表,算法,链表,数据结构

加法是从后加到前,而链表是从前往后。

栈实现

首先可以想到用栈先进后出的性质,把链表压栈然后依次出栈,对应相加。如下:
其中,需要有一个变量carry记录其进位情况。
另外还需注意一点的是,为了保证结果链表的顺序是从数字高位到低位的,我们在往结果链表添节点时需要使用头插法。
接下来考虑循环进入条件。当两个栈有一个非空时,进入循环;如果某一个栈结点已空,而另一栈某结点非空,则让空结点值为0即可。
还要考虑结果比原来最大位数还大一位的情况,如5+5.此时也要说明如果进位不为0时,还需要进行一次循环。
【算法手记03】反转链表,算法,链表,数据结构
代码如下:

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {  
    Stack<ListNode> s1 = new Stack<>();  
    Stack<ListNode> s2 = new Stack<>();  
    while (l1!=null){  
        s1.push(l1);  
        l1 = l1.next;  
    }  
    while (l2!=null){  
        s2.push(l2);  
        l2= l2.next;  
    }  
    int carry = 0;  
    ListNode dummy = new ListNode();  
    while (!s1.isEmpty() || !s2.isEmpty()||carry!=0){  
        int num1 = s1.isEmpty()?0:s1.pop().val;  
        int num2 = s2.isEmpty()?0:s2.pop().val;  
        //计算结果  
        int res = num1+num2+carry;  
        //计算进位  
        carry = res>=10?1:0;  
        res %=10;  
        //头插结果链表  
        ListNode resNode = new ListNode(res);  
        ListNode next = dummy.next;  
        dummy.next = resNode;  
        resNode.next = next;  
    }  
    return dummy.next;  
  
}

反转链表实现

逻辑类似。注意两点:文章来源地址https://www.toymoban.com/news/detail-826557.html

  1. 先抽象出链表反转子函数。
  2. 每加完一次,记得移动链表指针至next。
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {  
    l1 = reverse(l1);  
    l2 = reverse(l2);  
    int carry = 0;  
    ListNode dummy = new ListNode();  
    while (l1!=null || l2!=null || carry!=0){  
        int num1 ,num2;  
        if(l1!=null){  
            num1 = l1.val;  
            l1 = l1.next;  
        }else {  
            num1 = 0;  
        }  
        if(l2!=null){  
            num2 = l2.val;  
            l2 = l2.next;  
        }else {  
            num2 = 0;  
        }  
        int res = num1+num2+carry;  
        carry = res>=10?1:0;  
        res %= 10;  
        ListNode resNode = new ListNode(res);  
        ListNode next = dummy.next;  
        dummy.next = resNode;  
        resNode.next = next;  
    }  
    return dummy.next;  
  
}  
private ListNode reverse(ListNode head){  
    ListNode prev = null;  
    ListNode cur = head;  
    while (cur!=null){  
        ListNode next = cur.next;  
        cur.next = prev;  
        prev = cur;  
        cur = next;  
    }  
    return prev;  
}

到了这里,关于【算法手记03】反转链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索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)
  • 数据结构和算法-2023.07.03

      由于工作量加大,加之每天要写博客的内容上,深度可能没有那么深度了,但是为了保持这个日更的习惯,还是要坚持更新一些,我也发现了,其实写这个博文,更让我从某种程度上我重新的安静下来,重新的去理解和审视之前学习过的知识,之前的薄弱点在哪里,即使在

    2024年02月12日
    浏览(47)
  • 【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)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包