package A;

import java.util.Stack;

public class Manage1 {
    private Box head=new Box(0,"");

    public Box getHead() {
        return head;
    }

    public void add(Box box){
        Box temp=head;
        while (true){
            if (temp.next==null){
                break;
            }
            temp=temp.next;
        }
        temp.next=box;
    }

    public void printList(){
        Box temp=head.next;
        if (temp==null){
            System.out.println("链表是空的");
            return;
        }
        while (true){
            if (temp==null){
                break;
            }
            System.out.println(temp);
            temp=temp.next;
        }
    }

    public void addByOrder(Box box){
        Box temp=head;
        boolean flag=false;
        while (true){
            if (temp.next==null){
                break;
            }
            if (temp.next.id>box.id){
                break;
            }else if (temp.next.id==box.id){
                flag=true;
                break;
            }
            temp=temp.next;
        }
        if (flag){
            System.out.println("此标点已经存在");
        }else {
            box.next=temp.next;
            temp.next=box;
        }
    }
    public void upDate(Box box){
        Box temp=head.next;
        boolean flag=false;
        while (true){
            if (temp==null){
                break;
            }else if (temp.id==box.id){
                flag=true;
                break;
            }
            temp=temp.next;
        }
        if (flag){
            temp.name=box.name;
        }else {
            System.out.println("no exist!");
        }
    }
    public void reMove(int number){
        Box temp=head.next;
        boolean flag=false;
        while (true){
            if (temp==null){
                break;
            }else if (temp.id==number){
                flag=true;
                break;
            }
            temp=temp.next;
        }
        if (flag){
            temp.next=temp.next.next;
        }else {
            System.out.println("没有这个结点");
        }
    }
    public int getLength(Box head){
        Box cur=head.next;
        if (cur==null){
            return 0;
        }
        int length=0;
        while (cur!=null){
            length++;
            cur=cur.next;
        }
        return length;
    }
    public Box findLastIndexNode(Box head,int index) {//新浪
        Box cur=head.next;
        if (cur==null){
            return null;
        }
        int size=getLength(head);
        if (index>size||index<=0){
            System.out.println("格式不符");
            return null;
        }
        for (int i = 0; i < size - index; i++) {//3  1  2
            cur=cur.next;
        }
        return cur;
    }
    public void inVersion(Box head){//单链表的反转,腾讯面试题
        if(head.next==null||head.next.next==null){
            return;
        }
        Box reverse =new Box(0,"");
        Box next=null;
        Box cur=head.next;
        while (cur!=null){
            next=cur.next;
            cur.next=reverse.next;
            reverse.next=cur;
            cur=next;
        }
        head.next=reverse.next;
    }
    public void reversePrint(Box head){//单链表反向输出，百度面试题
        Stack<Box> stack=new Stack<>();
        Box cur=head.next;
        if (cur==null){
            System.out.println("链表是空的");
            return;
        }
        while (cur!=null){
            stack.push(cur);
            cur=cur.next;
        }
        while (stack.size()>0){
            System.out.println(stack.pop());
        }
    }
}

package A;

public class List {
    public static void main(String[] args) {
        Box one=new Box(1,"A");
        Box two=new Box(2,"AB");
        Box three=new Box(3,"ABC");
        Box four=new Box(4,"ABCD");
        Manage1 manage1=new Manage1();
        manage1.addByOrder(one);
        manage1.addByOrder(four);
        manage1.addByOrder(three);
        manage1.addByOrder(three);
        manage1.addByOrder(two);
        manage1.printList();

        System.out.println("==============");

        manage1.inVersion(manage1.getHead());
        manage1.printList();
        System.out.println("====");
        manage1.reversePrint(manage1.getHead());

        /*System.out.println("华丽分割");

        Box five=new Box(3,"ADS");
        manage1.upDate(five);
        manage1.printList();

        System.out.println("==============");
        manage1.reMove(1);
        //manage1.reMove(1);
        //manage1.reMove(1);
        //manage1.reMove(1);

        manage1.printList();

        System.out.println("==");
        System.out.println(manage1.getLength(manage1.getHead()));
        System.out.println("==");
        Box res=manage1.findLastIndexNode(manage1.getHead(),3);
        System.out.println(res);//倒数第三个*/


    }
}

package A;

public class Box {
    public int id;
    public String name;
    public Box next;

    public Box(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Box{" +
                "id=" + id +
                ", name=‘" + name + ‘\‘‘ +
                ‘}‘;
    }
}

单链表