JAVA-3.链表

package LinkedList_3;

import org.junit.Test;

/**
 * 链表(带头结点):对象即节点
 *
 * @author GoodTime0313
 * @version 1.0
 * @date 2021/1/23 0:54
 */
public class SingleLinkedList {
    //3.测试
    @Test
    public void test() {
        SingleLinkedListAdmin listAdmin = new SingleLinkedListAdmin();
        listAdmin.addTail(new Node(1, 1));
        listAdmin.addTail(new Node(2, 2));
        listAdmin.addTail(new Node(3, 3));
        listAdmin.delete(3);
        listAdmin.list();
    }
}

//1.定义节点类
class Node {
    public int number;
    public int age;
    public Node next;

    public Node(int number, int age) {
        this.age = age;
        this.number = number;
    }

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

//2.定义一个管理类管理链表的操作
class SingleLinkedListAdmin {
    //初始化头结点
    private Node head = new Node(0, 0);

    //添加结点(尾插法)
    public void addTail(Node newNode) {
        //head结点不能动需要一个辅助结点往下遍历
        Node temp = head;
        //将temp移动到链尾
        while (temp.next != null) {
            temp = temp.next;
        }
        //表尾temp指向新结点
        temp.next = newNode;
    }

    /*添加结点(头插法)
    public void addFirst(Node newNode){
        newNode.next = head.next;
        head.next = newNode;
    }*/

    //删除某一结点
    public void delete(int number) {
        Node temp = head;
        while (temp.next.number != number) {
            temp = temp.next;
            if (temp.next == null) {
                System.out.println("不存在number");
                return;
            }
        }
        temp.next = temp.next.next;
    }

    //显示全部结点
    public void list() {
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        Node temp = head.next;
        while (temp != null) {
            System.out.println(temp.number + " " + temp.age);
            temp = temp.next;
        }
    }
}

    public int getLength() {
        if (head.next == null) {
            return 0;
        }
        int len = 0;
        while (head.next != null) {
            len++;
            head = head.next;
        }
        return len;
    }

    public Node getK(int k) {
        if (head.next == null) {
            return null;
        }
        int len = 0;
        Node cur = head;
        while (cur.next != null) {
            len++;
            cur = cur.next;
        }
        if (k <= 0 || k > len) {
            return null;
        }
        Node cur2 = head;
        for (int i = 0; i < len - k; i++) {
            cur2 = cur2.next;
        }
        return cur2;
    }

    public void reversetList() {
        Node dummy = new Node(0,0);
        Node pCur = head;
        while (pCur != null) {
            //pNex保存下一次要插入的节点
            Node pNex = pCur.next;
            
            /*头插法*/
            //把pCur插入到dummy中
            pCur.next = dummy.next;
            //纠正头结点dummy的指向
            dummy.next = pCur;

            //pCur指向下一次要插入的节点
            pCur = pNex;
        }
        head=dummy;
    }

    public void reversePrint(){
        if (head.next == null){
            System.out.println("空链表");
        }
        Stack<Node> stack = new Stack<>();
        Node  cur = head.next;
        while (cur != null){
            stack.push(cur);
            cur = cur.next;
        }
        while (stack.size()>0){
            System.out.println(stack.pop());
        }
    }