当前位置:首页 » 《随便一记》 » 正文

3道真题训练|学会链表的前世今生

112 人参与  2022年11月24日 15:13  分类 : 《随便一记》  评论

点击全文阅读


?很多朋友都问我学完基础知识以后怎样提高编程水平?当然是刷题啦!很多小伙伴都在纠结从哪里开始,今天给大家推荐一个身边朋友都在使用的刷题网站:点击进入牛客网刷题吧!

在这里插入图片描述

?‍♂️今天是Java + 经典算法进阶刷题的第五天,结合经典算法学习Java语法!一起升级打怪吧!!

文章目录

?第一题:反转链表1.题目描述2.示例3.个人思路分析4.题解 ?第二题:链表内指定区间反转1.题目描述2.示例3.个人思路分析4.题解 ?第三题:链表中的节点每k个一组翻转1.题目描述2.示例3.个人思路分析4.题解 四. 总结(刷题经验分享)

?第一题:反转链表

?原题:反转链表

1.题目描述

给定一个单链表的头结点pHead(该头节点是有值的,比如在下图,它的val是1),长度为n,反转该链表后,返回新链表的表头。

数据范围: 0≤n≤1000
要求:空间复杂度 O(1) ,时间复杂度 O(n)。

如当输入链表{1,2,3}时,经反转后,原链表变为{3,2,1},所以对应的输出为{3,2,1}。

以上转换过程如下图所示:
在这里插入图片描述

2.示例

示例1

输入: {1,2,3}
返回值: {3,2,1}

示例2

输入: {}
返回值: {}

说明:空链表则输出空

3.个人思路分析

双链表求解是把原链表的结点一个个摘掉,每次摘掉的链表都让他成为新的链表的头结点,然后更新新链表。下面以链表1→2→3→4为例画个图来看下:
在这里插入图片描述

继续往下看:
在这里插入图片描述

他每次访问的原链表节点都会成为新链表的头结点,最后再来看下代码:

4.题解

Java版本代码实现:

public ListNode ReverseList(ListNode head) {    //新链表    ListNode newHead = null;    while (head != null) {        //先保存访问的节点的下一个节点,保存起来        //留着下一步访问的        ListNode temp = head.next;        //每次访问的原链表节点都会成为新链表的头结点,        //其实就是把新链表挂到访问的原链表节点的        //后面就行了        head.next = newHead;        //更新新链表        newHead = head;        //重新赋值,继续访问        head = temp;    }    //返回新链表    return newHead;}

?第二题:链表内指定区间反转

?原题:链表内指定区间反转

1.题目描述

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转,要求时间复杂度 O(n),空间复杂度 O(1)。

例如:

给出的链表为 1→2→3→4→5→NULL, m=2,n=4m=2,n=4,
返回 1→4→3→2→5→NULL.

数据范围: 链表长度 0<size≤1000,0 < m ≤n ≤ size,链表中每个节点的值满足 ∣val∣≤1000 。

要求:时间复杂度 O(n),空间复杂度 O(n)
进阶:时间复杂度 O(n),空间复杂度 O(1)

2.示例

示例1

输入: {1,2,3,4,5},2,4
返回值: {1,4,3,2,5}

示例2

输入: {5},1,1
返回值: {5}

3.个人思路分析

在学会了反转链表之后,要解决这个问题就很简单了,前一题是整个链表反转,这一题是部分反转,这上一题就是这道题的前置问题啊。那我们肯定是要先找到了第m个位置才能开始反转链表,而反转的部分就是从第m个位置到第n个位置,反转这部分的时候就参照上面第一题的反转链表:

在这里插入图片描述

4.题解

Java版本代码实现:

import java.util.*;public class Solution {    public ListNode reverseBetween (ListNode head, int m, int n) {        //加个表头        ListNode res = new ListNode(-1);        res.next = head;        //前序节点        ListNode pre = res;        //当前节点        ListNode cur = head;        //找到m        for(int i = 1; i < m; i++){            pre = cur;            cur = cur.next;        }        //从m反转到n        for(int i = m; i < n; i++){            ListNode temp = cur.next;            cur.next = temp.next;            temp.next = pre.next;            pre.next = temp;        }        //返回去掉表头        return res.next;    }}

?第三题:链表中的节点每k个一组翻转

?原题:链表中的节点每k个一组翻转

1.题目描述

将给出的链表中的节点每 k 个一组翻转,返回翻转后的链表:

如果链表中的节点数不是 k 的倍数,将最后剩下的节点保持原样
你不能更改节点中的值,只能更改节点本身。

数据范围:0 0≤n≤2000 ,1 ≤k≤ 2000 ,链表中每个元素都满足 0≤val≤1000

要求空间复杂度 O(1),时间复杂度 O(n) 。

例如

给定的链表是 1→2→3→4→5
对于 k = 2 , 你应该返回 2→1→4→3→5
对于 k = 3 , 你应该返回 3→2→1→4→5

2.示例

示例1

输入: {1,2,3,4,5},2
返回值: {2,1,4,3,5}

示例2

输入: {},1
返回值: {}

3.个人思路分析

关于这道经典的算法题目,我的思路大概分一下几个步骤:

找到待翻转的k个节点(注意:若剩余数量小于 k 的话,则不需要反转,因此直接返回待翻转部分的头结点即可)。对其进行翻转。并返回翻转后的头结点(注意:翻转为左闭又开区间,所以本作的尾结点其实就是下一作的头结点)。对下一轮 k 个节点也进行翻转操作。将上一轮翻转后的尾结点指向下一轮翻转后的头节点,即将每一轮翻转的k的节点连接起来。

图解:

在这里插入图片描述

4.题解

Java版本代码实现:

public class Solution {    /**     *      * @param head ListNode类      * @param k int整型      * @return ListNode类     */    public ListNode reverseKGroup (ListNode head, int k) {        // write code here        ListNode cur = head;        int count = 0;        // 找到待反转的第k个结点        while (cur != null && count != k) {            cur = cur.next;            count++;        }        if (count == k) {            // 递归            cur = reverseKGroup(cur, k);            // 反转列表            while (count != 0) {                count--;                ListNode tmp = head.next;                head.next = cur;                cur = head;                head = tmp;            }            // 拼接后续的链表            head = cur;        }        return head;    }}

四. 总结(刷题经验分享)

Java基础学习主要以练习为主,很多朋友听完视频课程学会基础以后感觉对练手项目无从下手,这里推荐去牛客网看看,这里的IT题库内容很丰富,属于国内做的很好的IT学习网站,而且是课程+刷题+面经+求职+讨论区分享。

在这里插入图片描述
从基础开始练习,知识点编排详细,题目安排合理,题目表述以指导的形式进行。整个题单覆盖了java入门的全部知识点以及全部语法,通过知识点分类逐层递进,从基础开始到最后的实践任务,都会非常详细地指导你应该使用什么函数,应该怎么输入输出。

在这里插入图片描述牛客网还提供题解专区和讨论区会有大神提供题解思路,对新手玩家及其友好,有不清楚的语法,不理解的地方,看看别人的思路,别人的代码,也许就能豁然开朗。


点击全文阅读


本文链接:http://zhangshiyu.com/post/49060.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备12007198号-1