单链表

public class LinkedList {
    Node head = null;

    //头插
    public void headAdd(Object val){
        Node n = new Node(head,val);
        head = n;
    }

    //尾插
    public void tailAdd(Object val){
        Node n = new Node(null,val);
        Node p = head;
        while (p.next != null){
            p = p.next;
        }
        p.next = n;
    }

    //链表逆序，时间复杂度O(n),空间复杂度O(1)
    public void reverseList(){
        Node t = null, p = head;
        while (p != null){
            Node next = p.next;
            p.next = t;
            t = p;
            p = next;
        }
        head = t;
    }
    
    class Node{
        Node next;
        Object value;

        public Node(Node next, Object value) {
            this.next = next;
            this.value = value;
        }
    }

    @Override
    public String toString() {
        String str = "";
        Node p = head;
        while (p != null){
            str +=p.value;
            p = p.next;
        }
        return str;
    }

    public static void main(String[] args){
        LinkedList linkedList = new LinkedList();
        for (int i = 0; i < 10; i++) {
            linkedList.headAdd(i);
        }
        System.out.println(linkedList);
        linkedList.reverseList();
        System.out.println(linkedList);


        for (int i = 0; i < 10; i++) {
            linkedList.tailAdd(i);
        }
        System.out.println(linkedList);
        linkedList.reverseList();
        System.out.println(linkedList);

    }
}