【剧前爆米花--爪哇岛寻宝】Java实现无头单向非循环链表和无头双向链表与相关题目

news/2025/1/16 3:40:54/

作者：困了电视剧

专栏：《数据结构--Java》

文章分布：这是关于数据结构链表的文章，包含了自己的无头单向非循环链表和无头双向链表实现简单实现，和相关题目，想对你有所帮助。

 

 

目录

无头单向非循环链表实现

无头双向链表实现

链表的相关题目

移除链表元素

反转一个单链表

链表的中间结点

链表中倒数第k个结点

无头单向非循环链表实现

public class SingleLinkedList {static class Node {public int val;//存储的数据public Node next;//存储下一个节点的地址//public Node(){}public Node (int val) {this.val = val;}}public Node head;public int size=0;//头插法public void addFirst(int data){Node node = new Node(data);node.next=head;head = node;size++;}//尾插法public void addLast(int data){Node node = new Node(data);if ( head==null ){head=node;return;}Node tmp=head;while ( tmp.next!=null ){tmp=tmp.next;}tmp.next=node;size++;}//任意位置插入,第一个数据节点为0号下标public boolean addIndex(int index,int data){//先判断idx是否合法if ( index>size||index<0 ){return false;}if ( head==null ){return false;}Node node = new Node(data);Node cur=head;int cnt=0;while ( cnt!=index ){cur=cur.next;cnt ++;}node.next=cur.next;cur.next=node;return true;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){if ( head==null ){return false;}Node cur = head;while ( cur!=null ){if ( cur.val==key ){return true;}cur=cur.next;}return false;}//删除第一次出现关键字为key的节点public void remove(int key){if ( head==null ){return;}if ( head.val==key ){head=head.next;return;}Node cur = head;while ( cur.next!=null ){if ( cur.next.val==key ){cur.next=cur.next.next;return;}cur=cur.next;}}//删除所有值为key的节点public void removeAllKey(int key){if ( head==null ){return;}Node pre=head;Node cur=head.next;while ( cur!=null ){if ( cur.val==key ){cur=cur.next;pre.next=cur;}else{pre=cur;cur=cur.next;}}if ( head.val==key ){head=head.next;}return;}//得到单链表的长度public int size(){return this.size;}public void display(){if ( head==null ){return;}Node cur=head;while ( cur!=null ){System.out.println(cur.val+" ");}}public void clear(){head=null;}
}

无头双向链表实现

public class MyLinkedList {//内部类构造一个链表数据结构static class ListNode{public int val;public ListNode prev;public ListNode next;public ListNode(){}public ListNode(int val){this.val=val;}}private ListNode first;private ListNode last;private int size=0;MyLinkedList(){}//头插法public void addFirst(int data){ListNode node=new ListNode(data);if ( first==null ){first=node;last=node;}else{node.next=first;first.prev=node;first=node;}size++;}//尾插法public void addLast(int data){ListNode node=new ListNode(data);if ( first==null ){first=node;last=node;}else{last.next=node;node.prev=last;last=node;}size++;}//任意位置插入,第一个数据节点为0号下标public boolean addIndex(int index,int data){//判断这个index是否合法if ( index<0 || index>size ){return false;}ListNode node=new ListNode(data);ListNode cur=first;for ( int i=0;i<index;i++ ){cur=cur.next;}if ( cur==first ){node.next=cur;cur.prev=node;first=node;}else if ( cur==last ){last.next=node;node.prev=last;last=node;}else{node.next=cur;node.prev=cur.prev;cur.prev.next=node;cur.prev=node;}return true;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){ListNode cur=first;while ( cur!=null ){if ( cur.val==key ){return true;}cur=cur.next;}return false;}//删除第一次出现关键字为key的节点public void remove(int key){ListNode cur=first;while ( cur!=null ) {if (cur.val == key) {//判断是不是头或尾if (cur == first) {first=first.next;if ( first!=null ){first.prev=null;}} else if (cur == last) {last=last.prev;last.next=null;} else {cur.prev.next=cur.next;cur.next.prev=cur.prev;}return;}cur = cur.next;}}//删除所有值为key的节点public void removeAllKey(int key){ListNode cur=first;while ( cur!=null ) {if (cur.val == key) {//判断是不是头或尾if (cur == first) {first=first.next;if ( first!=null ){first.prev=null;}} else if (cur == last) {last=last.prev;last.next=null;} else {cur.prev.next=cur.next;cur.next.prev=cur.prev;}}cur = cur.next;}}//得到单链表的长度public int size(){return this.size;}//输出链表的内容public void display(){ListNode cur=first;while ( cur != null ){System.out.println(cur.val);cur=cur.next;}}public void clear(){first=null;last=null;}
}

链表的相关题目

移除链表元素

https://leetcode.cn/problems/remove-linked-list-elements/description/

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

反转一个单链表

https://leetcode.cn/problems/reverse-linked-list/description/

将每一个结点的指向翻转一下，不需要重新遍历什么的。

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

链表的中间结点

https://leetcode.cn/problems/middle-of-the-linked-list/description/

用快慢指针可以在O(n)的时间复杂度完成。

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

链表中倒数第k个结点

https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a?tpId=13&&tqId=11167&rp=2&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking

用快慢指针的方法，快指针先跑k个，然后慢指针和快指针再按相同的速度跑 

public class Solution {public ListNode FindKthToTail(ListNode head,int k) {if ( head == null ){return null;}ListNode fast = head;ListNode slow = head;while (k != 0){if (fast != null){fast = fast.next;k--;}else{return null;}}while ( fast != null ){slow = slow.next;fast = fast.next;}return slow;}
}

 


http://www.ppmy.cn/news/31299.html

相关文章

前端面试题--JavaScript篇

前端面试题--JavaScript篇

一、JavaScript中的数据类型JavaScript中共有八种数据类型&#xff1a;Number、String、Boolean、Object、Null、Undefined、null、Symbol、BigInt 其中Symbol和BigInt是ES6新增的数据类型Symbol代表独一无二且不可改变的数据类型&#xff0c;主要为了解决可能出现的全局变量冲…
阅读更多...
Hive中order by，sort by，distribute by，Cluster by

Hive中order by，sort by，distribute by，Cluster by

order by 对数据进行全局排序, 只有一个reducer Task, 效率低 mysql中strict模式下, order by必须要有limit, 不然会拒绝执行. 对于分区表, 必须显示指定分区字段查询。 sort by 可以有多个reduce Task(以distribute by后的字段个数为准) 每个reduce Task内部数据有序, 但…
阅读更多...
脑机接口科普0018——前额叶切除手术

脑机接口科普0018——前额叶切除手术

本文禁止转载&#xff01;&#xff01;&#xff01; 首先说明一下&#xff0c;前额叶切除手术&#xff0c;现在已经不允许做了。 其次&#xff0c;前额叶切除手术&#xff0c;发明这个手术的人居然还获得了诺贝尔奖。太过于讽刺。1949年的那次诺贝尔医学奖&#xff08;就是我…
阅读更多...
载荷台子使用方式

载荷台子使用方式

载荷自动测量台子使用方法 电源开关旋转到1&#xff0c;开启电源开启台子微机开关&#xff0c;开启电脑&#xff08;winxp&#xff09;开启台子载荷开关&#xff0c;启动载荷台子点击电脑动标图标&#xff0c;开启软件放入载荷&#xff0c;弹性体向上&#xff0c;载荷台子压头压…
阅读更多...
【数据结构】研究链表带环问题

【数据结构】研究链表带环问题

&#x1f4af;&#x1f4af;&#x1f4af;&#x1f4af; 本篇主要研究的是链表带环问题&#xff0c;快慢指针的应用&#xff0c;分析不同解法对带环链表的处理&#xff0c;梳理完本篇你将对链表的理解更加透彻Ⅰ.研究链表带环问题Ⅱ.扩展带环问题1.为什么慢指针和快指针一定会相…
阅读更多...
学习ForkJoin

学习ForkJoin

学习ForkJoin一、普通解决多线程方式1、案例一2、效果图二、ForkJoin一、普通解决多线程方式 1、案例一 大数据量的List问题处理&#xff0c;多线程分批处理&#xff0c;需要解决的问题&#xff1a; 下标越界。线程安全。数据丢失。 private static ThreadPoolExecutor thre…
阅读更多...
反转链表相关的练习（下）

反转链表相关的练习（下）

目录 一、回文链表 二、 重排链表 三、旋转链表 一、回文链表 给你一个单链表的头节点 head &#xff0c;请你判断该链表是否为回文链表。如果是&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例 1&#xff1a; 输入&#xff1a;head [1,2,2,1] 输…
阅读更多...
云原生安全2.X 进化论系列|云原生安全2.X未来展望（4）

云原生安全2.X 进化论系列|云原生安全2.X未来展望（4）

随着云计算技术的蓬勃发展&#xff0c;传统上云实践中的应用升级缓慢、架构臃肿、无法快速迭代等“痛点”日益明显。能够有效解决这些“痛点”的云原生技术正蓬勃发展&#xff0c;成为赋能业务创新的重要推动力&#xff0c;并已经应用到企业核心业务。然而&#xff0c;云原生技…
阅读更多...
最新文章

Copyright @ 2022~2023