【LeeCode】链表的学习

基础知识

​​学习参考​​

import java.util.*;
// JAVA 链表
class Node {
    public int data;
    public Node next;
    public Node(int data){
        this.data = data;
    }
}

public class Main {

    public Node head;   // 表示单链表的头结点

    public void creatList(){
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;

        this.head = node1;
    }

    public void display(){
        Node cur = this.head;
        while (cur != null){
            System.out.print(cur.data + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    public int length(){
        Node cur = this.head;
        int count = 0;
        while (cur != null){
            count++;
            cur = cur.next;
        }
        System.out.println("count: " + count);
        return count;
    }

    public boolean contains(int key){
        Node cur = this.head;
        while (cur != null){
            if (cur.data == key){
                System.out.println("Contain: " + key + ", " + "Result: true");
                return true;
            }
            cur = cur.next;
        }
        System.out.println("Contain: " + key + ", " + "Result: false");
        return false;
    }

    public void addFirst(int key){
        Node node = new Node(key);

        if (this.head == null){
            this.head = node;
            return;
        }else {
            Node cur = this.head;
            node.next = cur;
            this.head = node;
        }
    }

    public void addLast(int key){
        Node cur = this.head;
        Node node = new Node(key);

        if (cur == null){
            this.head = node;
            return;
        }else {
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }
    }

    public Node searchPre(int index){
        Node cur = this.head;
        int count = 0;
        while (count != index-1){  // index-1 就是前一个节点
            cur = cur.next;
            count++;
        }
        return cur;
    }

    public Node searchPreNode(int index){
        Node cur = this.head;
        while (cur.next != null){
            if (cur.next.data == index){
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    public void addIndex(int index, int data){
        if (index < 0 || length() > length()){
            throw new RuntimeException("插入位置错误");
        }

        if (index == 0){
            addFirst(data);
        }

        if (index == length()){
            addLast(data);
        }

        Node node = searchPre(index);
        Node n1 = new Node(data);
        n1.next = node.next;
        node.next = n1;
    }

    public void remove(int index){
        if (this.head == null) return;
        if (this.head.data == index){
            this.head = this.head.next;
        }
        // 站到删除节点的前一个节点
        Node cur = searchPreNode(index);
        if (cur == null) {
            System.out.println("没有要删除的节点");
        }
        // 获取当前节点后, 修改指向
        Node del = cur.next;
        cur.next = del.next;
    }
    // 删除所有值为key的节点
    public void removeAllKey(int key){
        // 如果为空，则直接返回
        if (this.head == null){
            return;
        }

        Node pre = this.head;
        Node cur = this.head.next;

        while (cur != null){
            if (cur.data == key){
                pre.next = cur.next;
                cur = cur.next;
            }else {
                pre = cur;
                cur = cur.next;
            }
        }
        // 最后判断头结点
        if (this.head.data == key){
            this.head = this.head.next;
        }
    }

    public void clear(){
        while (this.head != null){
            Node next = this.head.next;
            this.head.next = null;
            this.head = next;
        }
    }

    public static void main(String[] args) {
        Main m1 = new Main();
        m1.creatList();
        m1.display();
        m1.length();
        m1.addFirst(0);
        m1.addLast(6);
        m1.length();
        m1.searchPreNode(5);
        m1.display();
    }
}