无头单向非循环链表实现 and leetcode刷题

无头单向非循环链表实现

  • 1. 单链表的模拟实现
    • IList.java接口：
    • MySingleList.java文件：
  • 2. leetcode刷题
    • 2.1 获取链表的中间节点
    • 2.2 删除链表中所有值为value的元素
    • 2.3 单链表的逆置
    • 2.4 获取链表倒数第k个节点
    • 2.5 给定 x, 把一个链表整理成前半部分小于 x, 后半部分大于等于 x 的形式
    • 2.6 判定链表是否是回文
    • 2.7 判定链表相交并求出交点
    • 2.8 判断链表带环
    • 2.9 求环的入口点
    • 2.10 合并两个有序链表

写在最前面，学习数据结构一定要结合画图！先画图分析，写出伪代码，再仔细分析伪代码是否成立，成立再写入题目中检验！

1. 单链表的模拟实现

单链表的模拟实现需要创建三个文件：IList.java接口文件，MySingleList.java文件，还有一个test.java测试文件。测试文件这里就不演示了。

IList.java接口：

public interface IList {
    // 1、无头单向非循环链表实现
        //头插法
        void addFirst(int data);
        //尾插法
        void addLast(int data);
        //任意位置插入,第一个数据节点为0号下标
        void addIndex(int index,int data);
        //查找是否包含关键字key是否在单链表当中
        boolean contains(int key);
        //删除第一次出现关键字为key的节点
        void remove(int key);
        //删除所有值为key的节点
        void removeAllKey(int key);
        //得到单链表的长度
        int size();
        void clear();
        void display();
}

MySingleList.java文件：

public class MySingleList implements IList{
    static class ListNode {
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;

    public void creatList() {
        ListNode node1 = new ListNode(0);
        ListNode node2 = new ListNode(1);
        ListNode node3 = new ListNode(2);
        ListNode node4 = new ListNode(3);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        head = node1;
    }

    @Override
    public void display() {
        ListNode cur = head;
        while (cur != null) {
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    @Override
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        node.next = head;
        head = node;
    }

    @Override
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        if(head == null) {
            head = node;
            return;
        }
        //找尾
        ListNode cur = head;
        while(cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;
    }

    @Override
    public void addIndex(int index, int data) {
        if(index < 0 || index > size()) {
            System.out.println("index位置不合法！");
            return;
        }
        if(index == 0) {
            addFirst(data);
            return;
        }
        if(index == size()){
            addLast(data);
            return;
        }
        ListNode node = new ListNode(data);
        ListNode cur = head;
        for (int i = 0; i < index-1; i++) {
            cur = cur.next;
        }
        node.next = cur.next;
        cur.next = node;
    }

    @Override
    public boolean contains(int key) {
        ListNode cur = head;
        while(cur != null) {
            if(cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

    @Override
    public void remove(int key) {
        if(head == null) {
            return;
        }
        if(head.val == key) {
            head = head.next;
            return;
        }
        ListNode pre = head;
        while(pre.next != null) {
            if(pre.next.val == key) {
                ListNode del = pre.next;
                pre.next =del.next;
                return;
            }
            pre = pre.next;
        }
    }


    @Override
    public void removeAllKey(int key) {
        if(head == null) {
            return;
        }
        ListNode pre = head;
        ListNode cur = head.next;
        while(cur != null) {
            if(cur.val == key) {
                pre.next = cur.next;
            }else {
                pre = cur;
            }
            cur = cur.next;
        }
        //该if语句只能放在最后面，如果头节点需要删除，
        //删除后有可能下一个节点（此时这个节点做头节点）依然是需要删除的
        //因此，只能放在最后，当后面的都删除好了，再检查头节点是否需要删除
        if(head.val == key) {
            head = head.next;
        }
    }

    @Override
    public int size() {
        int len = 0;
        ListNode cur = head;
        while(cur != null) {
            cur = cur.next;
            len++;
        }
        return len;
    }

    @Override
    public void clear() {
        head = null;
    }
}

2. leetcode刷题

2.1 获取链表的中间节点

题目链接：876. 链表的中间结点

注意：题目中说明当链表只有一个中间结点时，返回该节点；而当该链表有两个中间结点，返回第二个结点

解析：定义一对“快慢指针”，“快指针”为fast，一次走两步；“慢指针”为slow，一次走一步。

  • 当链表的结点个数为奇数个时，fast走到fast.next == null时，slow此时所在位置就是中间节点
  • 当链表的节点个数为偶数个时，fast走到fast == null时，slow此时所在位置就是中间节点

代码如下：

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

2.2 删除链表中所有值为value的元素

题目链接：203. 移除链表元素

这题的题解和模拟实现单链表的removeAllKey是一样的，故不再赘述。

代码如下：

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        if(head == null) {
            return head;
        }
        ListNode pre = head;
        ListNode cur = head.next;
        while(cur != null) {
            if(cur.val == val) {
                pre.next = cur.next;
            }else {
                pre = cur;
            }
            cur = cur.next;
        }
        if(head.val == val) {
            head = head.next;
        }
        return head;
    }
}

2.3 单链表的逆置

题目链接：206. 反转链表

解析：只需将链表的每个箭头调转方向即可，即修改当前节点的next值为前一个节点的地址，修改后就无法获取下一个节点了，故需要一个curN来定位下一个节点，又由于是单链表，无法得到前一个节点的位置，所以还需要定义一个prev来定位前一个节点的位置

在这里插入图片描述
代码如下：

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode pre = head;
        ListNode cur = head.next;
        ListNode curN = head.next.next;
        pre.next = null;
        while(cur != null) {
            cur.next = pre;
            pre = cur;
            cur = curN;
            if(curN != null) {
                curN = curN.next;
            }
        }
        return pre;
    }
}

2.4 获取链表倒数第k个节点

题目链接：面试题 02.02. 返回倒数第 k 个节点

解析：定义一对“快慢指针”，”快指针“fast先走k步，然后”快指针“fast和”慢指针“slow一起一次走一步，直至fast == null结束，这时slow指向的便是倒数第k个节点

代码如下：

class Solution {
    public int kthToLast(ListNode head, int k) {
        if(head == null) {
            return -1;
        }
        ListNode fast = head;
        ListNode slow = head;
        for(int i = 0; i < k; i++) {
            fast = fast.next;
        }
        while(fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow.val;
    }
}

2.5 给定 x, 把一个链表整理成前半部分小于 x, 后半部分大于等于 x 的形式

题目链接：CM11 链表分割

注意：这题是将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序

public class Partition {
    public ListNode partition(ListNode head, int x) {
        // write code here
        if(head == null) {
            return null;
        }
        ListNode bs = null;//bs:beforestart
        ListNode be = null;//be:beforeend
        ListNode as = null;//as:afterstart
        ListNode ae = null;//ae:afterend
        ListNode cur = head;
        while(cur != null) {
            if(cur.val < x) {
                if(bs == null) {//找到bs和be的起始位置
                    bs = be = cur;
                }else {
                    be.next = cur;
                    be = cur;
                }
            }else {
                if(as == null) {//找到as和ae的起始位置
                    as = ae = cur;
                }else {
                    ae.next = cur;
                    ae = cur;
                }
            }
            cur = cur.next;
        }
        //ae的next需要手动置为null
        if(ae != null) {
            ae.next = null;
        }
        //如果链表的节点都大于x，则返回as
        if(bs == null) {
            return as;
        }
        //bs不为null，be自然也不为空
        be.next = as;
        return bs;
    }
}

2.6 判定链表是否是回文

题目链接：OR36 链表的回文结构

public class PalindromeList {
    public boolean chkPalindrome(ListNode A) {
        // write code here
        if(A == null) {
            return false;
        }
        if(A.next == null) {
            return true;
        }
        //1.找到中间节点
        ListNode mid = getMiddleNode(A);
        //2.反转后半部分
        ListNode as = reseverList(mid);
        mid.next = null;//一定要置null！
        //3.从前往后依次对比两个链表的val值是否相同
        ListNode bs = A;
        while(bs.next != null && as.next != null) {
            if(bs.val != as.val) {
                return false;
            }
            bs = bs.next;
            as = as.next;
        }
        if(bs.val != as.val) {
            return false;
        }
        return true;
    }
    private ListNode reseverList(ListNode head) {
        ListNode prev = head;
        ListNode cur = head.next;
        ListNode curN = cur.next;
        while(cur != null) {
            cur.next = prev;
            prev = cur;
            cur = curN;
            if(curN != null){
                curN = curN.next;
            }
        }
        return prev;
    }
    private ListNode getMiddleNode(ListNode A) {
        ListNode fast = A;
        ListNode slow = A;
        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

2.7 判定链表相交并求出交点

题目链接：160. 相交链表

解题思路：

  1. 分别求出两个链表的长度，并得到两链表的长度差值（正数）
  2. 先让长链表的“l指针”走长度差值步，再让“l指针”和“s指针”一起走，如果相遇，相遇点即为相交链表的交点，如果没有相遇，则最后l和s同时为null
  3. 检验当两个链表同时为null时，代码是否满足

代码如下：

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = size(headA);
        int lenB = size(headB);
         //先假设headA链表的长度大于headB链表
        ListNode l = headA;
        ListNode s = headB;
        int len = lenA-lenB;
        //如果是headB链表更长，则进入if语句，进行调换
        if(len < 0) {
            len = -len;
            l = headB;
            s = headA;
        }
        for(int i = 0; i < len; i++) {
            l = l.next;
        }
        while(l != s) {
            l = l.next;
            s = s.next;
        }
        if(l == null) {
            return null;//没相交
        }
        return l;
    }
    public int size(ListNode head) {
        int len = 0;
        ListNode cur = head;
        while(cur != null) {
            cur = cur.next;
            len++;
        }
        return len;
    }
}

2.8 判断链表带环

题目链接：141. 环形链表

解题思路：

  1. 定义一对“快慢指针”，快指针fast一次走两步，慢指针slow一次走一步
  2. 如果最后fast == slow，则说明该链表存在环形结构；如果最后 fast == null || fast.next == null，则说明该链表不存在环形结构
  3. 检验链表为null时，代码是否满足

代码如下：

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

2.9 求环的入口点

题目链接：142. 环形链表 II

解题思路：

  1. 先判断链表结构中是否存在环（在2.8代码中进行略微修改即可）
  2. 求交点: 让一个引用从链表起始位置开始，一个引用从相遇点位置开始，两个引用每次都走一步，最终相遇时的节点即为交点（原因如下）

数学推导：
在这里插入图片描述
代码如下：

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语句必须放在下面，否则该if语句第一次就会成立，
            //因为fast和slow第一次都是head
            if(fast == slow){
                break;
            }
        }
        if(fast == null || fast.next == null) {
            return null;
        }
        slow = head;
        while(fast != slow) {
            fast = fast.next;
            slow = slow.next;
        }
        return fast;
    }
}

2.10 合并两个有序链表

题目链接：21. 合并两个有序链表

解题思路：

  1. 创建一个带头结点的单链表
  2. 依次对比两个链表的数值大小，小的尾插到新链表尾部
  3. 当一个链表被新链表连接完时，另一个链表剩下的部分直接尾插到新链表的尾部
  4. 检验当一个链表为null时，代码是否满足

代码如下：

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode cur1 = list1;
        ListNode cur2 = list2;
        ListNode newHead = new ListNode();//NewHead为带头结点
        ListNode curN = newHead;
        while(cur1 != null && cur2 != null) {
            if(cur1.val < cur2.val) {
                curN.next = cur1;
                cur1 = cur1.next;
            } else {
                curN.next = cur2;
                cur2 = cur2.next;
            }
            curN = curN.next;
        }
        if(cur1 == null) {
            curN.next = cur2;
        }
        if(cur2 == null) {
            curN.next = cur1;
        }
        return newHead.next;
    }
}

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

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

相关文章

【C++】C++书店管理系统（源码+论文）【独一无二】

【C++】C++书店管理系统（源码+论文）【独一无二】

&#x1f449;博__主&#x1f448;&#xff1a;米码收割机 &#x1f449;技__能&#x1f448;&#xff1a;C/Python语言 &#x1f449;公众号&#x1f448;&#xff1a;测试开发自动化【获取源码商业合作】 &#x1f449;荣__誉&#x1f448;&#xff1a;阿里云博客专家博主、5…
阅读更多...
如何在 Python 中创建一个类似于 MS 计算器的 GUI 计算器

如何在 Python 中创建一个类似于 MS 计算器的 GUI 计算器

问题背景 假设我们需要创建一个类似于微软计算器的 GUI 计算器。这个计算器应该具有以下功能&#xff1a; 能够显示第一个输入的数字。当按下运算符时&#xff0c;输入框仍显示第一个数字。当按下第二个数字时&#xff0c;第一个数字被替换。 解决方案 为了解决这个问题&am…
阅读更多...
mysql高可用解决方案：MHA原理及实现

mysql高可用解决方案：MHA原理及实现

MHA&#xff1a;Master High Availability。对主节点进行监控&#xff0c;可实现自动故障转移至其它从节点&#xff1b;通过提升某一从节点为新的主节点&#xff0c;基于主从复制实现&#xff0c;还需要客户端配合实现&#xff0c;目前MHA主要支持一主多从的架构&#xff0c;要…
阅读更多...
STL（一）

STL（一）

书写形式&#xff1a;string (const string& str, size_t pos, size_t len npos); 举例&#xff1a; int main(){ string url("https://mp.csdn.net/mp_blog/creation/editor?spm1000.2115.3001.4503") string sub1(url,0,5);//从下标为0开始向后5个字符&…
阅读更多...
07列的完整性约束

07列的完整性约束

文章目录 设置表字段的主键约束设置表字段的外键约束（FOREIGN KEY，FK）、设置表字段的非空约束（NOT NULL, NK）设置表字段唯一约束（UNIQUE，UK）设置表字段值自动增加（AUTO_INCREMENT）设置表字段的默认值（DEFAULT）修改默认值DEFAULT、自增长和非空NK设置表字段的主键约…
阅读更多...
30.ROM-IP核的调用

30.ROM-IP核的调用

&#xff08;1&#xff09;ROM IP核简介&#xff1a; ROM是只读存储器&#xff0c;是一种只能读出事先锁存的固态半导体存储器。其特性是一旦存储资料就无法再将之改变或删除&#xff0c;并且资料也不会因为电源关闭而消失。&#xff08;掉电不丢失&#xff09; FPGA使用内部RA…
阅读更多...
JavaScript青少年简明教程：为何学习JavaScript及JavaScript简介

JavaScript青少年简明教程：为何学习JavaScript及JavaScript简介

JavaScript青少年简明教程&#xff1a;为何学习JavaScript及JavaScript简介 JavaScript最初是为web浏览器&#xff08;前端开发&#xff09;设计的。它可以在所有现代浏览器中运行&#xff0c;包括Chrome, Firefox, Safari, Edge等。 这意味着JavaScript代码可以在任何能运行…
阅读更多...
学习测试7-ADB的使用

学习测试7-ADB的使用

ADB是什么&#xff1f; ADB&#xff0c;即 Android Debug Bridge&#xff08;安卓调试桥&#xff09; 是一种允许模拟器或已连接的 Android 设备进行通信的命令行工具&#xff0c;它可为各种设备操作提供便利&#xff0c;如安装和调试应用&#xff0c;并提供对 Unix shell&…
阅读更多...
数据（图像）增广

数据（图像）增广

一、数据增强 1、增加一个已有数据集&#xff0c;使得有更多的多样性&#xff0c;比如加入不同的背景噪音、改变图片的颜色和形状。 2、增强数据是在线生成的 3、增强类型&#xff1a; &#xff08;1&#xff09;翻转 &#xff08;2&#xff09;切割 &#xff08;3&#xf…
阅读更多...
MessageBox与HubSpot：企业沟通与客户管理的双重利器

MessageBox与HubSpot：企业沟通与客户管理的双重利器

今天咱们来聊聊两个超实用的工具——MessageBox和HubSpot。它们就像是你的超级助手&#xff0c;让你和客户沟通起来更顺畅&#xff0c;管理起来也更轻松。 先说说MessageBox吧 想象一下&#xff0c;你正在忙着工作&#xff0c;突然客户发来个消息&#xff0c;你嗖的一下就收到…
阅读更多...
实验场：在几分钟内使用 Bedrock Anthropic Models 和 Elasticsearch 进行 RAG 实验

实验场：在几分钟内使用 Bedrock Anthropic Models 和 Elasticsearch 进行 RAG 实验

作者&#xff1a;来自 Elastic Joe McElroy, Aditya Tripathi 我们最近发布了 Elasticsearch Playground&#xff0c;这是一个新的低代码界面&#xff0c;开发人员可以通过 A/B 测试 LLM、调整提示&#xff08;prompt&#xff09;和分块数据来迭代和构建生产 RAG 应用程序。今天…
阅读更多...
github恢复码怎么备份

github恢复码怎么备份

https://docs.github.com/zh/authentication/securing-your-account-with-two-factor-authentication-2fa/configuring-two-factor-authentication-recovery-methods
阅读更多...
电商IP分类及其应用是什么？

电商IP分类及其应用是什么？

在现代电商运营中&#xff0c;IP地址不仅是网络通信的基础&#xff0c;也扮演着关键的角色&#xff0c;支持多种功能和应用场景。本文将介绍几种常见的电商IP分类&#xff0c;以及它们在电商领域中的具体应用。 1. 前台IP与后台IP 电商网站在运营过程中通常需要区分前台IP和后…
阅读更多...
数据不可修改 确保数据安全-GS备份存储方案防病毒防勒索

数据不可修改 确保数据安全-GS备份存储方案防病毒防勒索

为保障企业关键数据不被病毒或勒索软件侵害&#xff0c;通过Veeam数据不可变功能&#xff0c;存储内数据更安全
阅读更多...
【计算机组成原理 | 第三篇】各个硬件的组成部分

【计算机组成原理 | 第三篇】各个硬件的组成部分

前言&#xff1a; 在前面的文章中&#xff0c;我们介绍了计算机架构的基本组成。可以知道计算机的基本架构由“存储器”&#xff0c;“运算器”&#xff0c;“控制器”&#xff0c;“输入设备”&#xff0c;“输出设备”这五部分组成。 在这片文章中&#xff0c;我们来深入的了…
阅读更多...
【若依管理系统】注意事项

【若依管理系统】注意事项

1.前端字段必填 rules: {sceneName: [{ required: true, message: "场景名称不能为空", trigger: "blur" }],orderNum: [{ required: true, message: "显示排序不能为空", trigger: "blur" }], }, 2.IDEA&#xff0c;默认以debug模式…
阅读更多...
dive deeper into tensor:从底层开始学习tensor

dive deeper into tensor:从底层开始学习tensor

inspired by karpathy/micrograd: A tiny scalar-valued autograd engine and a neural net library on top of it with PyTorch-like API (github.com)and Taking PyTorch for Granted | wh (nrehiew.github.io). 这属于karpathy的karpathy/nn-zero-to-hero: Neural Networks…
阅读更多...
数据库系统原理练习 | 作业2-第2章关系数据库（附答案）

数据库系统原理练习 | 作业2-第2章关系数据库（附答案）

整理自博主本科《数据库系统原理》专业课完成的课后作业&#xff0c;以便各位学习数据库系统概论的小伙伴们参考、学习。 *文中若存在书写不合理的地方&#xff0c;欢迎各位斧正。 专业课本&#xff1a; 目录 一、选择题 二、填空题 三、简答题 四、关系代数 1.课本p70页&…
阅读更多...
插片式远程 I/O模块：Profinet总线耦合器在SIMATIC Manager配置

插片式远程 I/O模块：Profinet总线耦合器在SIMATIC Manager配置

XD9000是Profinet总线耦合器&#xff0c;单个耦合器最多可扩展32个I/O模块&#xff01;本文将详细介绍如何在SIMATIC Manager中配置插片式远程 I/O模块的Profinet总线耦合器&#xff0c;帮助您更好地应用这一技术。 一、SIMATIC Manager软件组态步骤&#xff1a; 1、创建工程&…
阅读更多...
bevfomer self-att to transformer to tensorrt

bevfomer self-att to transformer to tensorrt

self-attentation https://blog.csdn.net/weixin_42110638/article/details/134016569 query input* Wq key input* Wk value input* Wv output 求和 query . key * value detr multiScaleDeformableAttn Deformable Attention Module&#xff0c;在图像特征上&#…
阅读更多...
最新文章

Copyright @ 2022~2023