JAVA链表相关习题2

1.反转一个单链表。

. - 力扣（LeetCode）

 //2在1前面

//1在3前面

//ListNode cur=head.next

//head.next=null(翻转后头节点变为最后一个节点)

// while(cur != null) {
            //记录 当前需要翻转节点的下一个节点
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;

//要求：时间复杂度O(n),空间复杂度O(1)，就地翻转

//利用头插法

public ListNode reverseList() {
        if(head == null) {
            return null;
        }
        if(head.next == null) {
            return head;
        }
        //处理本身是第一个节点的节点
        ListNode cur = head.next;
        head.next = null;
        while(cur != null) {
            //记录 当前需要翻转节点的下一个节点
            ListNode curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }

2.快慢指针

2.1给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。  

876. 链表的中间结点 - 力扣（LeetCode）

/**
 * 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 middleNode(ListNode head) {
        if(head==null){
            return null;
        }
        if(head.next==null){
            return head;
        }
        ListNode slow=head;
        ListNode fast=head;
        while(fast !=null&&fast.next!=null){//注意二者不可以互换
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
}

 

//如果是在面试的高度，并不仅仅是结果的问题，还要看具体的做法是否为优。

//空间复杂度O(1)

//使用快慢指针

//路程一样，fast一次走两步，slow一次走一步，fast走完全程，slow一定在中间位置。

//循环条件：fast!=null&&fast.next!=null(顺序不能改变，否则会出现空指针异常)

//fast==fast.next.next;

//slow=slow.next;

2.2 找到链表的倒数第k个节点

思路：

 链表中倒数第k个结点__牛客网 (nowcoder.com)

/**
 * 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 removeNthFromEnd(ListNode head, int n) {
        if(n<=0 || head==null){
            return null;
        } 
        ListNode temp=head;
        int count=0;
        //判断有几个结点
        while(temp!=null){
            count++;
            temp=temp.next;
        }
        if(n==count){
            return head.next;
        }
        int c=count-n;
        temp=head;
        for(int i=0;i<c-1;i++){
            temp=temp.next;
        }//找到该节点
        temp.next=temp.next.next;
        return head;
        }
}

 

19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode） 

3.将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

. - 力扣（LeetCode）

 

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode newHead=new ListNode();//建立一个新的链表
        ListNode tmH=newHead;
        while(list1 !=null&&list2!=null){
            if(list1.val<list2.val){
                tmH.next=list1;
                tmH=tmH.next;
                list1=list1.next;
            }
            else{
                tmH.next=list2;
                tmH=tmH.next;
                list2=list2.next;
            }
        }
        if(list1!=null){
            tmH.next=list1;
        }
        if(list2!=null){
            tmH.next=list2;
        }
        return newHead.next;
    }
}

 4.编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结点之前 。

//保证原来顺序不变，采用尾插法

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        // write code here
        ListNode bs = null;
        ListNode be = null;
        ListNode as = null;
        ListNode ae = null;
        ListNode cur = pHead;
        while (cur != null) {
            if (cur.val < x) {
                if (bs == null) {
                    bs = cur;
                    be = cur;
                } else {
                    be.next = cur;
                    be = cur;
                    //cur = cur.next;省略1
                }
                //cur = cur.next; 省略2
            } else {
                //第一次插入的时候
                if (as == null) {
                    as = cur;
                    ae = cur;
                } else {
                    ae.next = cur;
                    ae = cur;
                }
            }
            cur = cur.next;
        }

        if (bs == null) {
            return as;
        }
        //把两个链表连到一起
        be.next = as;
        if (as != null) {
            ae.next = null;
        }
        return bs;
    }
}

5. 链表的回文结构。

链表的回文结构_牛客题霸_牛客网

//正着反着遍历的结果是一致的

//只需要将链表后半部分进行翻转

1.找到链表的中间 节点


2.翻转中间节点以后的链表


3.从前 从后 开始比较

 

import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        // write code here
        if (A == null)
            return false;
        //1、找中间节点
        ListNode fast = A;
        ListNode slow = A;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        //slow所指的位置就是中间节点
        //2、开始翻转
        ListNode cur = slow.next;
        while (cur != null) {
            ListNode curNext = cur.next;//记录下一个节点
            cur.next = slow;
            slow = cur;
            cur = curNext;
        }
        //此时翻转完成
        //3、开始判断是否为回文
        while (A != slow) {//中间位置结束的条件
            if (A.val != slow.val) {
                return false;
            }
            //偶数节点
            if (A.next == slow) {
                return true;
            }
            A = A.next;
            slow = slow.next;
        }
        return true;
    }
}

6.输入两个链表，找出它们的第一个公共结点。 

. - 力扣（LeetCode）

相交一定是“Y”字型，不可能是“X”字型

后面的链表是一样的

1.相交是Y子型
2.两个链表长度 不一样 主要体现在相交之前

3.可以先让 最长的 链表的引用 先走他们的差值步。

//分别求两个链表的长度

 

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA==null&&headB!=null){
            return null;
        }
        if(headB==null&&headA!=null){
            return null;
        }
        ListNode plong = headA;//假设A长
        ListNode pshort = headB;

        //1、分别求两个链表的长度

        int len1 = 0;
        int len2 = 0;
        
        while (plong != null) {
             len1++;
             plong = plong.next;
        }
        //O(N)
        while (pshort != null) {
            len2++;
            pshort = pshort.next;
        }
        plong = headA;
        pshort = headB;
        //2、求差值步的len
        int len = len1 - len2;
        if(len < 0) {
            plong = headB;
            pshort = headA;
            len = len2 - len1;
        }
        //保证plong 一定指向最长的链表  pshort一定指向最短的链表  len一定是一个正数
        //3、链表长的走len步
        while (len != 0) {
            plong = plong.next;
            len--;
        }
        //4、一起走,根据next值判断相遇！
        while (plong != pshort) {
            plong = plong.next;
            pshort = pshort.next;
        }
        return plong;
    }
}

 7.给定一个链表，判断链表中是否有环。

【思路】
快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表起始位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。比如：陪女朋友到操作跑步减肥。
【扩展问题】
为什么快指针每次走两步，慢指针走一步可以？
假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在慢指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。
快指针一次走 3 步，走 4 步， ...n 步行吗？

. - 力扣（LeetCode）

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null || head.next==null){
            return false;
        }
        ListNode slow=head;
        ListNode fast=head.next;
        while(slow!=fast){
            if(fast==null || fast.next==null){
                return false;
            }
            slow=slow.next;
            fast=fast.next.next;
        }
        return true;
    }
}

8.删除链表中重复的结点

删除链表中重复的结点_牛客题霸_牛客网 (nowcoder.com)

import java.util.*;
/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        ListNode cur=pHead;
        ListNode newHead=new ListNode(-1);
        ListNode tempHead=newHead;
        //遍历链表中的每个结点
        while(cur!=null){
            if(cur.next!=null&&cur.val==cur.next.val){
                //一直让cur走到不重复的节点，然后把这个节点加到不重复的链表中
                while(cur.next!=null&&cur.next.val==cur.val){
                    cur=cur.next;
                }
                cur=cur.next;
            }else{
                tempHead.next=cur;
                tempHead=tempHead.next;
                cur=cur.next;
            }
        }
        tempHead.next=null;
        return newHead.next;
    }
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/606662.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

谷粒商城实战(022 业务-订单模块-服务调用)

谷粒商城实战(022 业务-订单模块-服务调用)

Java项目《谷粒商城》架构师级Java项目实战&#xff0c;对标阿里P6-P7&#xff0c;全网最强 总时长 104:45:00 共408P 此文章包含第267p-第p270的内容 远程调用 订单服务调用客户服务的查询收货地址信息方法 1.在订单服务里添加EnableFeignClients 来开启远程调用功能 2.…
阅读更多...
【Scala---04】函数式编程 『 函数 vs 方法 | 函数至简原则 | 函数式编程』

【Scala---04】函数式编程 『 函数 vs 方法 | 函数至简原则 | 函数式编程』

文章目录 1. 函数 vs 方法1.1 方法(1) 定义方法(2) 运算符即方法 1.2 函数(1) 定义函数(2) 匿名函数 1.3 方法转为函数1.4 可变参数&默认参数 2. 函数至简原则3. 函数式编程3.1 函数式编程思想3.3 函数柯里化&闭包3.5 递归 & 尾递归 4. 补充4.1 访问元祖元素4.2 &g…
阅读更多...
TCP 连接，一端断电和进程崩溃有什么区别？

TCP 连接，一端断电和进程崩溃有什么区别？

TCP 连接&#xff0c;一端断电和进程崩溃有什么区别&#xff1f; 前言主机崩溃进程崩溃有数据传输的场景客户端主机宕机&#xff0c;又迅速重启客户端主机宕机&#xff0c;一直没有重启 总结 前言 有的小伙伴在面试腾讯的时候&#xff0c;遇到了这么个问题&#xff1a; 这个属…
阅读更多...
一键审计 web 日志（teler）

一键审计 web 日志（teler）

在 web 系统遭受攻击之后&#xff0c;通常要审计 web 日志来寻找蛛丝马迹&#xff0c;那么有没有可以满足需求的自动化工具呢&#xff1f;今天就来尝试一款开源工具 teler&#xff0c;项目地址&#xff1a; https://github.com/kitabisa/teler/ 先来看一张作者测试图&#xff1…
阅读更多...
NPDP|传统行业产品经理如何跨越鸿沟，从用户角度审视产品

NPDP|传统行业产品经理如何跨越鸿沟，从用户角度审视产品

随着科技的飞速发展和互联网的普及&#xff0c;产品经理的角色已经从单纯的产品规划者逐渐转变为全方位的用户体验设计者。对于传统行业的产品经理来说&#xff0c;这是一个挑战与机遇并存的时代。他们不仅要面对激烈的市场竞争&#xff0c;还要学会如何跨越与新兴科技行业之间…
阅读更多...
一行Python代码可以做什么，超出你想象

一行Python代码可以做什么，超出你想象

哈喽&#xff0c;大家好&#xff0c;我是木头左&#xff01; 揭秘编程语言的灵活性 在编程的世界里&#xff0c;简洁就是力量。Python以其优雅和简洁而著称&#xff0c;让开发者能够用更少的代码做更多的事。但这并不意味着功能上的妥协——Python的强大之处在于它允许在一行代…
阅读更多...
【基于 PyTorch 的 Python 深度学习】5 机器学习基础（3）

【基于 PyTorch 的 Python 深度学习】5 机器学习基础（3）

前言 文章性质&#xff1a;学习笔记 &#x1f4d6; 学习资料&#xff1a;吴茂贵《 Python 深度学习基于 PyTorch ( 第 2 版 ) 》【ISBN】978-7-111-71880-2 主要内容&#xff1a;根据学习资料撰写的学习笔记&#xff0c;该篇主要介绍了单 GPU 加速和多 GPU 加速&#xff0c;以及…
阅读更多...
今年做电商，视频号小店绝对是明智之举，未来风口就在这里

今年做电商，视频号小店绝对是明智之举，未来风口就在这里

大家好&#xff0c;我是电商笨笨熊 电商一直是近几年的热门创业方向&#xff1b; 但是面对众多电商平台&#xff0c;对于普通玩家的我们来说&#xff0c;该怎么选择呢&#xff1f; 今年来说&#xff0c;我会更愿意选择视频号小店。 作为一个腾讯推出的电商项目&#xff0c;…
阅读更多...
LeetCode例题讲解:移动044

LeetCode例题讲解:移动044

给定一个数组 nums&#xff0c;编写一个函数将所有 0 移动到数组的末尾&#xff0c;同时保持非零元素的相对顺序。 请注意 &#xff0c;必须在不复制数组的情况下原地对数组进行操作。 示例 1: 输入: nums [0,1,0,3,12] 输出: [1,3,12,0,0] 示例 2: 输入: nums [0] 输出…
阅读更多...
【STM32+HAL】DS18B20读取环境温度

【STM32+HAL】DS18B20读取环境温度

一、准备工作 有关CUBEMX的初始化配置&#xff0c;参见我的另一篇blog&#xff1a;【STM32HAL】CUBEMX初始化配置 二、所用工具 1、芯片&#xff1a; STM32F407VET6 2、IDE&#xff1a; MDK-Keil软件 3、库文件&#xff1a;STM32F4xxHAL库 三、实现功能 串口打印当前温度值…
阅读更多...
Day_3

Day_3

1. HttpClient HttpClient是Apache的一个子项目&#xff0c;是高效的、功能丰富的支持HTTP协议的客户端编程工具包 作用&#xff1a;发送HTTP请求&#xff0c; 接受相应数据 <dependency><groupId>org.apache.httpcomponents</groupId><artifactId>…
阅读更多...
Deep Learn Part Six Gated RNN-24.5.1

Deep Learn Part Six Gated RNN-24.5.1

本章核心一句话&#xff1a; 卸下包袱&#xff0c;轻装上阵。--尼采 总述&#xff1a;本章所学内容 0.引子&#xff1a; 上一章介绍的 RNN 之所以不擅长学习时序数据的长期依赖关系&#xff0c;是因为 BPTT 会发生梯度消失和梯度爆炸的问题。本节我们将首先回顾一下上一章介…
阅读更多...
21物联1班shift五次

21物联1班shift五次

1.选择推荐选项 2.等待 3.点击取消 4.选择查看问题详细信息 5.点击txt文件 6.找到system文件夹&#xff0c;将sethc改为qqq&#xff0c;将cmd文件改为sethc文件 7.单击完成。重新启动虚拟机。连续按五次shift出现cmd框&#xff0c;修改密码
阅读更多...
MySql#MySql安装和配置

MySql#MySql安装和配置

目录 一、卸载不需要的环境 二、安装mysql yum 源 三、开始安装 四、如果保证安装成功呢&#xff1f; 五、MySql 启动&#xff01; 六、登录mysql 七、配置文件说明 八、设置开机启动&#xff01; 本次安装是在Linux环境在centos7中完成 首先先将自己切换成root 一、…
阅读更多...
彻底搞懂大小端存储and调试中内存窗口如何使用？

彻底搞懂大小端存储and调试中内存窗口如何使用？

定义 首先我们有一个常识&#xff0c;Windows采用小端存储方式。 探究Windows下vs2019是什么存储&#xff1f; 在小端存储方式中&#xff0c;低字节存储在内存的低地址处&#xff0c;高字节存储在内存的高地址处。这与大端存储方式恰好相反&#xff0c;大端存储方式中高字节存…
阅读更多...
[图解]DDD领域驱动设计浮夸，Eric Evans开了个坏头

[图解]DDD领域驱动设计浮夸，Eric Evans开了个坏头

0 00:00:00,630 --> 00:00:02,790 今天我们要讲的是 1 00:00:03,930 --> 00:00:07,420 DDD领域驱动设计浮夸 2 00:00:07,700 --> 00:00:10,590 Eric Evans开了个坏头 3 00:00:14,790 --> 00:00:17,380 在《领域驱动设计》的 4 00:00:18,650 --> 00:00:22,59…
阅读更多...
QT:小项目：登录界面 （下一章连接数据库）

QT:小项目：登录界面 （下一章连接数据库）

一、效果图 登录后&#xff1a; 二、项目工程结构 三、登录界面UI设计 四主界面 四、源码设计 login.h #ifndef LOGIN_H #define LOGIN_H#include <QDialog>namespace Ui { class login; }class login : public QDialog {Q_OBJECTpublic:explicit login(QWidge…
阅读更多...
暴露自己IP地址有什么危险

暴露自己IP地址有什么危险

暴露自己的IP地址确实存在一定的危险性&#xff0c;以下是关于这一问题的详细探讨&#xff1a; 一、IP地址的重要性 IP地址是互联网通信中的关键标识&#xff0c;它使得网络中的设备能够相互识别并进行数据传输。在网络世界中&#xff0c;每台设备都需要一个独特的IP地址来确…
阅读更多...
2024蓝桥杯CTF writeUP--packet

2024蓝桥杯CTF writeUP--packet

根据流量分析&#xff0c;我们可以知道129是攻击机&#xff0c;128被留了php后门&#xff0c;129通过get请求来获得数据 129请求ls Respons在这 里面有flag文件 这里请求打开flag文件&#xff0c;并以base64编码流传输回来 获得flag的base64的数据 然后解码 到手
阅读更多...
C语言 举例说明循环嵌套

C语言 举例说明循环嵌套

今天 我们来说循环的嵌套 如果一个循环体内 又包含了另一个循环结构 我们称之为循环的嵌套 我们之前学的 While do-while for 都可以进行相互的嵌套 如下图 在 While 循环语句中再嵌套一个 While 循环语句 do-while 中嵌套 do-while for中嵌套 for 例如 我们做一个九九乘法…
阅读更多...
最新文章

Copyright @ 2022~2023