算法记录lday4 LinkedList链表交换 删除倒数N个点 环形链表

今日任务

● 24. 两两交换链表中的节点
● 19.删除链表的倒数第N个节点
● 面试题 02.07. 链表相交
● 142.环形链表II

两两交换链表中的节点

题目描述

Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)
Swapping nodes in a linked list in pairs

在这里插入图片描述

link

https://leetcode.com/problems/swap-nodes-in-pairs/description/

思路 solution

difficult one
if you want to swap two node
you have to use one pointer pointer to the node before the first node of two nodes

处理两个节点
Handle two nodes
需要面对四个节点
Need to face four nodes

the node before these two nodes
the node after these two nodes

difficult two
when will the cur node stop
when the cur.next == null or cur.next.next == null
the while loop会停止

time and space complexity

loop through the whole linked list
the time complexity is O(n)
the space complexity is O(1)

在这里插入图片描述

coding

class Solution {
    public ListNode swapPairs(ListNode head) {
        
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode cur = dummy;

        while (cur.next != null && cur.next.next != null) {
            ListNode node2 = cur.next;
            ListNode node3 = cur.next.next;
            ListNode node4 = cur.next.next.next;

            cur.next = node3;
            node3.next = node2;
            node2.next = node4;

            cur = cur.next.next;
        }

        return dummy.next;
    }
}

删除链表的倒数第N个节点

delete the nth to the last node from linked list
Given the head of a linked list, remove the nth node from the end of the list and return its head.
在这里插入图片描述

link

https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/

思路 solution

这道题已经做了多次了
easy

create dummy node before head

use two pointer
one fast, one slow
for (int i = 0; i < k; i++)
move fast

and then move fast and slow both
untill fast move to the end

delete node in slow position

however, when you need to delete nth node
you need to find the n-1 th node and delete n node

therefore fast start from head
slow start from dummy

coding

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode fast = head, slow = dummy;

        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }

        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        slow.next = slow.next.next;

        return dummy.next;
    }
}

intersection of linkedlist 链表交叉

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

For example, the following two linked lists begin to intersect at node c1:
在这里插入图片描述

link

https://leetcode.com/problems/intersection-of-two-linked-lists/description/

solution 思路

easy 做过多次
use two pointer to iterate through these two linkedlist from the begaining
p1 start from the head of link1
p2 start from the head of link2
once p1 move the end of link1, it should start from the link2
same to p2

once p1 == p2, stop the while loop and return

time and space complexity

O(N + M)
n is len of list1
m is len of list2

coding

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA, p2 = headB;

        while (p1 != p2) {
            
            if (p1 != null) {
                p1 = p1.next;
            } else {
                p1 = headB;
            }

            if (p2 != null) {
                p2 = p2.next;
            } else {
                p2 = headA;
            }
        }

        return p1;
    }
}

另外一种常规思路
先统计出 长短
计算其中差值 k

然后让指向 长的链表的指针 先移动k步

然后再同时移动 两个指针

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA, p2 = headB;
        int len1 = 0, len2 = 0;

        while (p1 != null) {
            p1 = p1.next;
            len1++;
        }

        while (p2 != null) {
            p2 = p2.next;
            len2++;
        }

        int gap = 0;
        p1 = headA;
        p2 = headB;

        if (len1 > len2) {
            gap = len1 - len2;

            while (gap != 0) {
                gap--;
                p1 = p1.next;
            }

        } else {
            gap = len2 - len1;

            while (gap != 0) {
                gap--;
                p2 = p2.next;
            }
        }


        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }

        return p1;

    }
}

环形链表 Circular linked list

思路 solution

这道题做错了
I made a mistake in this question
错点在于 如何判断 存在环
The mistake lies in how to determine the existence of a ring
use while loop
the condiition is fast != null and fast.next != null
中间
当 slow == fast 的时候, break
然后判断

fast == null or fast.enxt == null
如果为null 则说明 没环直接返回

coding

public class Solution {
    public ListNode detectCycle(ListNode head) {

        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) break;
        }

        if (fast == null || fast.next == null) return null;

        // Entrance to the ring

        ListNode p1 = fast;
        ListNode p2 = head;

        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }

        return p1;
    }
}

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

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

相关文章

错题汇总03

1.以下对二维数组a进行正确初始化的语句是 A int a[2][]{{0,1,2},{3,4,5}} B int a[][3]{{0,1,2},{3,4,5}} C int a[2][4]{{0,1,2},{3,4},{5}}; D int a[][3]{{0,,2},{},{3,4,5}} A数组列不能省略 C数组越界 D数组初始化每一行必须连续初始化 2.能把函数处理结果的二个数据…

存储资源调优技术——SmartDedupe智能数据重删、SmartCompression智能数据压缩技术

目录 SmartDedupe智能数据重删技术 SmartCompression智能数据压缩技术 SmartDedupe智能数据重删技术 基本概念 智能数据重删技术 是一种数据缩减技术&#xff0c;通过删除存储系统中的冗余数据块 减少数据占用的物理存储容量&#xff0c;节省存储空间&#xff08;会降低性能&a…

【Java笔试强训 13】

&#x1f389;&#x1f389;&#x1f389;点进来你就是我的人了博主主页&#xff1a;&#x1f648;&#x1f648;&#x1f648;戳一戳,欢迎大佬指点! 欢迎志同道合的朋友一起加油喔&#x1f93a;&#x1f93a;&#x1f93a; 目录 一、选择题 二、编程题 &#x1f525;参数解析…

【YOLO系列】YOLOv7论文超详细解读(翻译 +学习笔记)

前言 终于读到传说中的YOLOv7了~≖‿≖✧ 这篇是在美团的v6出来不到一个月就高调登场&#xff0c;作者还是我们熟悉的AB大神&#xff08;对&#xff0c;就是v4那个&#xff09;&#xff0c;读起来又是“熟悉”的感觉&#xff08;贯穿了我的整个五一假期&#xff08;╯&#x…

Qt第一天:创建Qt项目

方式一&#xff1a;使用向导创建 打开Qt Creator 界面选择 New Project或者选择菜单栏 【文件】-【新建文件或项目】菜单项 弹出New Project对话框&#xff0c;选择Qt Widgets Application 选择【Choose】按钮&#xff0c;弹出如下对话框 设置项目名称和路径&#xff0c;按照…

软件测试:测试一个网站

一、软件测试的原则 1、软件测试应尽早执行&#xff0c;并贯穿于整个软件生命周期 2、软件测试应追溯需求 3、测试应由第三方来构造 4、穷举测试是不可能的,要遵循 Good-enough 原则 5、必须确定预期输出&#xff08;或结果&#xff09; 6、必须彻底检查每个测试结果 7、…

CH32V307V-EVT-R1 简单上手入门

文章目录 〇、前言一、开发板展示以及介绍二、开发环境配置与搭建2.1 IDE 介绍2.2 IDE 环境搭建2.3 IDE 配置2.3.1 语言切换&#xff08;汉化&#xff1f;不存在的&#xff09; 三、初次烧录与体验四、简单总结与心得&#x1f517; 链接直达 〇、前言 运气不错&#xff0c;前几…

Baklib推荐:关于建设企业知识管理的有效方法

随着信息化和互联网技术的不断发展&#xff0c;企业面临着海量的信息和知识&#xff0c;如何有效地管理和利用这些信息和知识已经成为了企业发展的关键问题之一。企业知识管理是指企业利用信息技术手段&#xff0c;对企业内部的知识进行系统化、集成化、共享化管理&#xff0c;…

4D毫米波雷达聚类检测和追踪

代码&#xff1a;https://github.com/Xiao-Hu-Z/RaderDetectionAndTracking 代码正在写&#xff0c;实时更新&#xff01; 流程 4D雷达毫米波聚类跟踪流程如下图&#xff1a; 预处理主要包括标定、坐标转换和动静分离。 标定使用水平仪、角反&#xff0c;采集数据分析&…

fastai2 实现SSD

https://github.com/search?qfastaissd 有几个值得参考的代码&#xff0c;好好学习。 GitHub - Samjoel3101/SSD-Object-Detection: I am working on a SSD Object Detector using fastai and pytorch fastai2实现的SSD&#xff0c;终于找到了code。https://github.com/sidrav…

【NLP实战】基于Bert和双向LSTM的情感分类【上篇】

文章目录 前言简介数据获取与提取数据清洗读取数据&#xff0c;查看数据清洗训练集观察数据分布去除空数据去除重复数据关于去除停用词关于特殊符号储存清洗后的数据集 清洗测试集观察数据分布去除空数据去除重复数据(并储存) 清洗验证集观察数据分布去除空行去除重复数据(并储…

16.基于主从博弈理论的共享储能与综合能源微网优化运行研究

说明书 MATLAB代码&#xff1a;基于主从博弈理论的共享储能与综合能源微网优化运行研究 关键词&#xff1a;主从博弈 共享储能 综合能源微网 优化调度 参考文档&#xff1a;《基于主从博弈理论的共享储能与综合能源微网优化运行研究》完全复现 仿真平台&#xff1a;MATLAB …

图解项目管理必备十大管理模型

请点击↑关注、收藏&#xff0c;本博客免费为你获取精彩知识分享&#xff01;有惊喜哟&#xff01;&#xff01; 心智模型 心智模型是根深蒂固存在于人们心中&#xff0c;影响人们如何理解这个世界&#xff08;包括我们自己、他人、组织和整个世界&#xff09;&#xff0c;以及…

pytest - Getting Start

前言 项目开发中有很多的功能&#xff0c;通常开发人员需要对自己编写的代码进行自测&#xff0c;除了借助postman等工具进行测试外&#xff0c;还需要编写单元测试对开发的代码进行测试&#xff0c;通过单元测试来判断代码是否能够实现需求&#xff0c;本文介绍的pytest模块是…

Android APK 反编译后重新打包并签名

APKTool&#xff1a; Apktool 是一个逆向android非常有用的工具&#xff0c;可以用来反编译apk文件&#xff0c;并且能在修改部分资源文件后&#xff0c;重新打包成一个新的apk。 下载连接&#xff1a;http://ibotpeaches.github.io/Apktool/install/ 下载之后文件夹非常清爽&…

ChatGPT会颠覆SEO内容创作吗

近几年 AI 的发展日新月异。除了搜索算法本身大规模应用人工智能&#xff0c;我也一直关注着 AI 用于写作的进展。 上篇关于 Google 有用内容更新的帖子还在说&#xff0c;高质量内容创作是 SEO 最难的事之一&#xff0c;对某些网站来说&#xff0c;如果能有工具帮助&#xff…

Mysql 日志

目录 0 课程视频 1 错误日志 -> 默认开启 1.1 查看变量 show variables like %log_error%; 1.2 文件位置 /var/log -> mysqld.log 1.3 指令语法 2 二进制日志 -> 修改数据和数据库结构的日志 2.1 记录原则 2.1.1 记录 数据库创建语句 和 增删改查 2.1.2 不记…

JdbcTemplate常用语句代码示例

目录 JdbcTemplate 需求 官方文档 JdbcTemplate-基本介绍 JdbcTemplate 使用实例 需求说明 创建数据库 spring 和表 monster 创建配置文件 src/jdbc.properties 创建配置文件 src/JdbcTemplate_ioc.xml 创建类JdbcTemplateTest测试是否可以正确得到数据源 配置 J…

智能算法系列之基于粒子群优化的模拟退火算法

文章目录 前言1. 算法结合思路2. 问题场景2.1 Sphere2.2 Himmelblau2.3 Ackley2.4 函数可视化 3. 算法实现代码仓库&#xff1a;IALib[GitHub] 前言 本篇是智能算法(Python复现)专栏的第四篇文章&#xff0c;主要介绍粒子群优化算法与模拟退火算法的结合&#xff0c;以弥补各自…

《基于EPNCC的脉搏信号特征识别与分类研究》阅读笔记

目录 一、论文摘要 二、论文十问 三、论文亮点与不足之处 四、与其他研究的比较 五、实际应用与影响 六、个人思考与启示 参考文献 一、论文摘要 为了快速获取脉搏信号的完整表征信息并验证脉搏信号在相关疾病临床诊断中的敏感性和有效性。在本文中&#xff0c;提出了一…
最新文章