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

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

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

🌏第一题：反转链表

🌄原题：反转链表

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

🌏第二题：链表内指定区间反转

🌄原题：链表内指定区间反转

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

要求：时间复杂度 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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

🌏第三题：链表中的节点每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.个人思路分析

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

1. 找到待翻转的k个节点（注意：若剩余数量小于 k 的话，则不需要反转，因此直接返回待翻转部分的头结点即可）。
2. 对其进行翻转。并返回翻转后的头结点（注意：翻转为左闭又开区间，所以本作的尾结点其实就是下一作的头结点）。
3. 对下一轮 k 个节点也进行翻转操作。
4. 将上一轮翻转后的尾结点指向下一轮翻转后的头节点，即将每一轮翻转的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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

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

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

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

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