算法与数据结构03：链表

• 反转单链表
• 反转双向链表
• 删除链表中指定的数的节点

public class List01 {

    public static class Node {
        public int value;
        public Node next;

        public Node(int data) {
            value = data;
        }
    }

    public static Node reverse(Node head) {
        Node pre = null;
        Node next = null;

        while (head != null) {
            next = head.next; // 保存当前head节点的后继节点
            head.next = pre; // head的后继指针指向pre节点
            pre = head; // 保存当前head节点的引用到pre
            head = next; // head指向下一个节点
        }

        // head指向null，跳出了循环，此时pre就是原来的尾结点，反转后的新头部节点
        return pre;
    }

}

public class List02 {

    public static class DoubleNode {
        public int value;
        public DoubleNode last;
        public DoubleNode next;

        public DoubleNode(int data) {
            value = data;
        }
    }

    public static DoubleNode reverse(DoubleNode head) {
        DoubleNode pre = null;
        DoubleNode next = null;
        while (head != null) {
            next = head.next; //保存head的下一个节点
            head.last = next; //修改head的last指针指向原next节点
            head.next = pre; //修改head的next指针指向原pre指针
            pre = head; //当前head节点赋值给pre
            head = next; //遍历下一个节点
        }

        return pre;
    }

}

public class List03 {

    public static class Node {
        public int value;
        public Node next;

        public Node(int data) {
            value = data;
        }
    }

    public static Node reverse(Node head, int num) {
        //如果头节点的值为给定的值，则一直删除，直到与给定值不等
        while (head != null && head.value == num) {
            head = head.next;
        }

        //此时的head的value必然与num不等
        Node pre = null;
        Node cur = null;

        while (cur != null) {
            if (cur.value == num) {
                pre.next = cur.next;
            } else {
                pre = cur;
            }
            cur = cur.next;
        }

        return head;
    }

}