数据结构（三）——LinkList与链表
1.链表
1.1链表的概念
链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。
1.2链表的结构
注意：
1.由此可得，链表在逻辑上是连续的，但是在物理上并不一定连续
2.现实中节点一般都是从堆上申请出来的，而每次从堆上申请的空间位置都是随机的。
1.3链表的实现
public class SingleLinkedList {
//初始化
private static class Node{
int value;
SingleLinkedList.Node next;
public Node(int value){this.value=value;}
}
//头节点
public SingleLinkedList.Node head;
//头插法
public void addFirst(int data){
SingleLinkedList.Node node=new SingleLinkedList.Node(data);
node.next=head;
head=node;
}
//尾插法
public void addLast(int data){
//首先new一个新节点
SingleLinkedList.Node node=new SingleLinkedList.Node(data);
//判断链表是否为空
if(head==null){
head=node;
return;
}
//临时变量current
SingleLinkedList.Node current=head;
while(current.next!=null){
current=current.next;//寻找尾节点
}
current.next=node;//将尾节点next域指向新节点进行连接
}
//任意位置插入,第一个数据节点为0号下标
public void addIndex(int index,int data){
checkIndex(index);
if(index==0){
addFirst(data);
return;
}
if(index==size()){
addLast(data);
return;
}
Node node=new Node(data);
Node prevNode=finprevNode(index);
node.next=prevNode.next;
prevNode.next=node;
}
public Node finprevNode(int index){
Node current=head;
for (int i = 0; i <(index-1); i++) {
current=current.next;
}
return current;
}
public void checkIndex(int index){
if(index<0||index>size()){
throw new IndexOutOfBoundsException("数组下标越界");
}
}
//查找是否包含关键字key是否在单链表当中
public boolean contains(int key){
SingleLinkedList.Node node=new SingleLinkedList.Node(key);
SingleLinkedList.Node current=head;
if(current!=null){
if(current.value==key){
return true;
}
current=current.next;
}
return false;
}
//删除第一次出现关键字为key的节点
public void remove(int key){
SingleLinkedList.Node current=head;
if(head.value==key){
head=head.next;
}
while(current!=null){
if(current.next.value==key){
current.next=current.next.next;
return;
}
current=current.next;
}
}
//删除所有值为key的节点
public void removeAllKey(int key){
if(head!=null){
}
SingleLinkedList.Node PrevNode=head;
SingleLinkedList.Node current=PrevNode.next;
while(current!=null){
if(current.value==key){
PrevNode.next=current.next;
}else{
PrevNode.next=current;
}
current=current.next;
}
if(head.value==key){
head=head.next;
}
}
//得到单链表的长度
public int size(){
SingleLinkedList.Node current=head;
int count=0;
while(current!=null){
current=current.next;
count++;
}
return count;
}
public void clear() {
Node current=head;
while(current!=null){
Node nextNode=current.next;
current.next=null;
current=nextNode;
}
head=null;
}
public void display() {
//定义一个临时变量替代head
SingleLinkedList.Node current=head;
StringBuilder sb=new StringBuilder();
sb.append("[");
while(current!=null) {
sb.append(current.value);
if(current.next!=null){
sb.append(",");
}
current=current.next;
}
sb.append("]");
System.out.println(sb);
}
}
测试用例：
public class Test {
public static void main(String[] args) {
SingleLinkedList linkedList=new SingleLinkedList();
//头插法尾插法测试
linkedList.addFirst(12);
linkedList.addFirst(8);
linkedList.addFirst(12);
linkedList.addFirst(2);
linkedList.addLast(32);
linkedList.addLast(8);
linkedList.display();
System.out.println("====================");
//测试任意位置插入
linkedList.addIndex(2,10);
linkedList.display();
System.out.println("====================");
//查找元素是否在链表中
System.out.println(linkedList.contains(12));
System.out.println(linkedList.contains(88));
System.out.println("====================");
//删除第一次出现的数据||删除链表中出现的所有数据
linkedList.remove(8);
linkedList.removeAllKey(12);
linkedList.display();
System.out.println("====================");
//得到链表长度
System.out.println(linkedList.size());
//清空链表
linkedList.clear();
linkedList.display();
}
}
输出结果：
1.4相关OJ题
======================如果需要相关oj题练习链接可以留言======================
1.4.1移除链表元素
题目：给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：head = [], val = 1 输出：[]
示例 2：
输入：head = [7,7,7,7], val = 7 输出：[]
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head==null){
return null;
}
ListNode current=head.next;
ListNode prve=head;
while(current!=null){
if(current.val==val){
prve.next=current.next;
}else{
prve=current;
}
current=current.next;
}
if (head.val == val) {
head = head.next;
}
return head;
}
}1.4.2单链表的逆置
题目：给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if (head==null){
return null;
}
ListNode current= head;
ListNode prev=null;
while(current!=null){
ListNode next=current.next;
current.next=prev;
prev=current;
current=next;
}
return prev;
}
}1.4.3链表的中间节点
题目：给定一个头结点为 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点
示例 1：
输入：[1,2,3,4,5]
输出：此列表中的结点 3 (序列化形式：[3,4,5])
返回的结点值为 3 。
示例 2：
输入：[1,2,3,4,5,6]
输出：此列表中的结点 4 (序列化形式：[4,5,6])
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode middleNode(ListNode head) {
if(head==null){
return null;
}
ListNode fast=head;
ListNode slow=head;
while(fast!=null&&fast.next!=null){
fast=fast.next.next;
slow=slow.next;
}
return slow;
}
}1.4.4获取链表倒数第k个节点
题目：输入一个链表，输出该链表中倒数第k个结点。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindKthToTail(ListNode head, int k) {
if (head == null || k <= 0) {
return null;
}
ListNode fast = head;
ListNode slow = head;
while (k - 1 > 0) {
fast = fast.next;
if (fast == null) {
return null;
}
k--;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}1.4.5合并两个有序链表
题目：将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if(list1==null){
return list2;
}
if(list2==null){
return list1;
}
ListNode temoNode=new ListNode(-1);//傀儡节点
ListNode current=temoNode;
while(list1!=null&&list2!=null){
if(list1.val<list2.val){
current.next=list1;
current=current.next;
list1=list1.next;
}else{
current.next=list2;
current=current.next;
list2=list2.next;
}
}
if(list1!=null){
current.next=list1;
}
if(list2!=null){
current.next=list2;
}
return temoNode.next;
}
}