一、链表介绍

本文主要用Java实现单链表，链表的查询时间复杂度为O(n)，增加的时间复杂度为O(n)，删除也为O(n)，链表的创建不需要所有的数据之间的创建空间是连续的，是简单的数据结构

二、java代码实现

1.创建节点

创建一个类用来定义链表的每一个节点，每一个节点包括value和next，value是当前节点的值，next为下一个节点的地址值（同样是Node类）

public class Node<T>{
    T value;
    Node next;

    public Node() {
    }

    public Node(T value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return "Node{" +
                "value=" + value +
                ", next=" + next +
                '}';
    }
}

2.链表的相关属性

头节点

头节点是链表的开始

public class NodeList {
    Node head;
}

链表的长度

头节点默认指向当前链表的第一个元素，如果直接修改head的话，会导致head的指向没有指向到正确的位置，所以所有涉及遍历的方法都需要重新定义一个节点和head头节点相同从而实现操作。

public int getLen(){
        Node node1 = head;
        int count = 0;
        while(node1 !=null){
            count++;
            node1 = node1.next;
        }
        return count;
    }

链表是否为空

    public boolean isEmpty(){
        return this.getLen() == 0;
    }

3.添加数据

头插法添加数据

头插法的时间复杂度为O(1)，在定义需要判断当前的头节点是否为空，如果为空的话，则直接赋值，否则则将插入的节点的下一个节点为头节点，并且将插入节点给头节点。

    public void HeadInsert(Node node){
        if(head == null){
            head = node;
        }
        node.next = head;
        head = node;
    }

尾插法添加数据

尾插法的时间复杂度为O(n)，在定义需要判断当前的头节点是否为空，如果为空的话，则直接赋值，否则将遍历到最后一个节点，并且将节点的next值指向要插入的节点值。

    public void LastInsert(Node node){
        if(head == null) {
            head = node;
            return;
        }

        Node current = head;
        while(current.next != null) {
            current = current.next;
        }

        current.next = node;
    }

任意位置添加数据

 public void InsertPostion(int index, Node node) {
        if (head == null && index == 0) {
            head = node;
            return;
        }
        Node current = head;
        int p = 0;
        Node pre = null;

        if (index == 0) {
            HeadInsert(node);
            return;
        }
        while (current != null) {
            if (p == index) {
                pre.next = node;
                node.next = current;
                return;
            }
            pre = current;
            current = current.next;
            p++;
        }
        System.out.println("Index out of bounds");
    }

4.查询元素

查询元素代码如下：

    public T search(T value){
        Node<T> current = head;
        while (current != null) {
            if (current.value.equals(value)) {
                return current.value;
            }
            current = current.next;
        }
        return null;
    }

5.以字符串数组的形式展示链表

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[");
        Node<T> current = head;
        while (current != null) {
            sb.append(current.value);
            if (current.next != null) {
                sb.append(",");
            }
            current = current.next;
        }
        sb.append("]");
        return sb.toString();
    }

三、删除元素

1、头节点删除元素

    public void HeadDelete(){
        if(head == null){
            throw  new RuntimeException("元素为空");
        }
        head = head.next;
    }

2、尾节点删除元素

    public void LastDelete() {
        if (head == null) {
            throw new RuntimeException("元素为空");
        }
        if (head.next == null) { 
            head = null;
            return;
        }
        Node<T> node = head;
        while (node.next != null && node.next.next != null) {
            node = node.next;
        }
        node.next = null;
    }

3、任意节点删除元素

    public void LastDelete() {
        if (head == null) {
            throw new RuntimeException("元素为空");
        }
        if (head.next == null) {
            head = null;
            return;
        }
        Node<T> node = head;
        while (node.next != null && node.next.next != null) {
            node = node.next;
        }
        node.next = null;
    }
    public void DeletePosition(int index) {
        if (head == null) {
            throw new RuntimeException("元素为空");
        }
        if (index == 0) {
            head = head.next;
            return;
        }

        Node<T> node = head;
        Node<T> pre = null;
        int i = 0;
        while (node != null && i < index) {
            pre = node;
            node = node.next;
            i++;
        }
        if (node == null) {
            throw new RuntimeException("Index out of bounds");
        }
        pre.next = node.next;
    }

4、任意元素全部删除元素

  public void delAll(T num) {
        if (head == null) {
            return; 
        }
        while (head != null && head.value.equals(num)) {
            head = head.next; 
        }
        Node<T> node = head;
        while (node != null && node.next != null) {
            if (node.next.value.equals(num)) {
                node.next = node.next.next;
            } else {
                node = node.next; 
            }
        }
    }

四、判断数组是否是环形的链表

力扣环形链表题

1、快慢指针

快慢指针的定义：定义两个指针一个node = node.next ,另一个node = node.next.next，因此有一个指针走速快，另一个指针走速慢，在一定时间之后就会相遇。

**public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        while (fast != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                return null;
            }
            if (fast == slow) {
                ListNode ptr = head;
                while (ptr != slow) {
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}

2、哈希表

哈希表常用做查重和去重的操作，因此也可以用来判断链表是否是环形链表

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode pos = head;
        Set<ListNode> visited = new HashSet<ListNode>();
        while (pos != null) {
            if (visited.contains(pos)) {
                return pos;
            } else {
                visited.add(pos);
            }
            pos = pos.next;
        }
        return null;
    }
}