public class ListNode {
    public int value;
    public ListNode next;
    
    public ListNode(int value) {
        this.value = value;
    }

}

public class Mylist {
    /**
     * 头结点插入
     */
    public static void headInsert(ListNode head, ListNode newHead) {
        ListNode old = head;
        head = newHead;
        head.next = old;
    }
    
    /**
     * 尾节点插入
     */
    public static void tailInsert(ListNode tail, ListNode newTail) {
        ListNode old = tail;
        tail = newTail;
        old.next = tail;
        newTail.next = null;
    }
    
    /**
     * 遍历
     */
    public static void traverse(ListNode head) {
        while(head != null) {
            System.out.print(head.value+" ");
            head = head.next;
        }
        System.out.println();
    }
    
    /**
     * 查找
     */
    public static int find(ListNode head, int value) {
        int index = -1;
        int count = 0;
        while(head != null) {
            if(head.value == value) {
                index = count;
                return count;
            }
            count++;
            head = head.next;
        }
        return index;
    }
    
    /**
     * 中间插入
     * @param oldNode
     * @param newNode
     */
    public static void insert(ListNode p, ListNode s) {
        ListNode next = p.next;
        p.next = s;
        s.next = next;
    }
    
    /**
     * 删除节点
     */
    public static void delete(ListNode head, ListNode q) {
        if(q != null) {
            if(q.next != null) {
                ListNode p = q.next;
                q.value = p.value;
                q.next = p.next;
                p = null;
            }else {//删除最后一个元素的情况
                while(head != null) {
                    if(head.next != null && head.next == q) {
                        head.next = null;
                        break;
                    }
                    head = head.next;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        ListNode node1 = new ListNode(1);
        ListNode node2 = new ListNode(2);
        ListNode node3 = new ListNode(3);
        
        node1.next = node2;
        node2.next = node3;
        node3.next = null;
        traverse(node1);
        //头结点插入
        ListNode newHead = new ListNode(0);
        headInsert(node1, newHead);
        traverse(newHead);
        //尾节点插入
        ListNode newTail = new ListNode(4);
        tailInsert(node3, newTail);
        traverse(newHead);
        //中间节点插入
        ListNode node = new ListNode(5);
        insert(node2, node);
        traverse(newHead);
        //删除非尾节点
        delete(node1, node);
        traverse(newHead);
        //删除尾节点
        delete(newHead, newTail);
        traverse(newHead);
    }
}