龙岩建设局升降机网站,免费发布推广的平台,两学一做的做题网站是多少,做暧昧的小视频网站2作者#xff1a;困了电视剧 专栏#xff1a;《数据结构--Java》 文章分布#xff1a;这是关于数据结构链表的文章#xff0c;包含了自己的无头单向非循环链表和无头双向链表实现简单实现#xff0c;和相关题目#xff0c;想对你有所帮助。 目录
无头单向非循环链表实现 … 作者困了电视剧 专栏《数据结构--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 size0;//头插法public void addFirst(int data){Node node new Node(data);node.nexthead;head node;size;}//尾插法public void addLast(int data){Node node new Node(data);if ( headnull ){headnode;return;}Node tmphead;while ( tmp.next!null ){tmptmp.next;}tmp.nextnode;size;}//任意位置插入,第一个数据节点为0号下标public boolean addIndex(int index,int data){//先判断idx是否合法if ( indexsize||index0 ){return false;}if ( headnull ){return false;}Node node new Node(data);Node curhead;int cnt0;while ( cnt!index ){curcur.next;cnt ;}node.nextcur.next;cur.nextnode;return true;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){if ( headnull ){return false;}Node cur head;while ( cur!null ){if ( cur.valkey ){return true;}curcur.next;}return false;}//删除第一次出现关键字为key的节点public void remove(int key){if ( headnull ){return;}if ( head.valkey ){headhead.next;return;}Node cur head;while ( cur.next!null ){if ( cur.next.valkey ){cur.nextcur.next.next;return;}curcur.next;}}//删除所有值为key的节点public void removeAllKey(int key){if ( headnull ){return;}Node prehead;Node curhead.next;while ( cur!null ){if ( cur.valkey ){curcur.next;pre.nextcur;}else{precur;curcur.next;}}if ( head.valkey ){headhead.next;}return;}//得到单链表的长度public int size(){return this.size;}public void display(){if ( headnull ){return;}Node curhead;while ( cur!null ){System.out.println(cur.val );}}public void clear(){headnull;}
}
无头双向链表实现
public class MyLinkedList {//内部类构造一个链表数据结构static class ListNode{public int val;public ListNode prev;public ListNode next;public ListNode(){}public ListNode(int val){this.valval;}}private ListNode first;private ListNode last;private int size0;MyLinkedList(){}//头插法public void addFirst(int data){ListNode nodenew ListNode(data);if ( firstnull ){firstnode;lastnode;}else{node.nextfirst;first.prevnode;firstnode;}size;}//尾插法public void addLast(int data){ListNode nodenew ListNode(data);if ( firstnull ){firstnode;lastnode;}else{last.nextnode;node.prevlast;lastnode;}size;}//任意位置插入,第一个数据节点为0号下标public boolean addIndex(int index,int data){//判断这个index是否合法if ( index0 || indexsize ){return false;}ListNode nodenew ListNode(data);ListNode curfirst;for ( int i0;iindex;i ){curcur.next;}if ( curfirst ){node.nextcur;cur.prevnode;firstnode;}else if ( curlast ){last.nextnode;node.prevlast;lastnode;}else{node.nextcur;node.prevcur.prev;cur.prev.nextnode;cur.prevnode;}return true;}//查找是否包含关键字key是否在单链表当中public boolean contains(int key){ListNode curfirst;while ( cur!null ){if ( cur.valkey ){return true;}curcur.next;}return false;}//删除第一次出现关键字为key的节点public void remove(int key){ListNode curfirst;while ( cur!null ) {if (cur.val key) {//判断是不是头或尾if (cur first) {firstfirst.next;if ( first!null ){first.prevnull;}} else if (cur last) {lastlast.prev;last.nextnull;} else {cur.prev.nextcur.next;cur.next.prevcur.prev;}return;}cur cur.next;}}//删除所有值为key的节点public void removeAllKey(int key){ListNode curfirst;while ( cur!null ) {if (cur.val key) {//判断是不是头或尾if (cur first) {firstfirst.next;if ( first!null ){first.prevnull;}} else if (cur last) {lastlast.prev;last.nextnull;} else {cur.prev.nextcur.next;cur.next.prevcur.prev;}}cur cur.next;}}//得到单链表的长度public int size(){return this.size;}//输出链表的内容public void display(){ListNode curfirst;while ( cur ! null ){System.out.println(cur.val);curcur.next;}}public void clear(){firstnull;lastnull;}
}
链表的相关题目
移除链表元素
https://leetcode.cn/problems/remove-linked-list-elements/description/
class Solution {public ListNode removeElements(ListNode head, int val) {if ( headnull ){return null;}ListNode prehead;ListNode curhead.next;while ( cur!null ){if ( cur.valval ){curcur.next;pre.nextcur;}else{precur;curcur.next;}}if ( head.valval ){headhead.next;}return head;}
}反转一个单链表
https://leetcode.cn/problems/reverse-linked-list/description/
将每一个结点的指向翻转一下不需要重新遍历什么的。
class Solution {public ListNode reverseList(ListNode head) {if ( headnull ){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?tpId13tqId11167rp2ru/activity/ojqru/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;}
}
