作者：困了电视剧

专栏：《数据结构--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

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;}
}

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;}
}

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;}
}

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;}
}