package wsj;
/**
 * 当前类所有函数
 * -------------
 * 生成单向链表：buildList()
 * 打印单向链表：printList()
 * 反转单向链表：reverseList()
 * 
 * 生成双向链表：buildDoubleList()
 * 打印双向链表：printList()
 * 反转双向链表：reverseList()
 */

// 定义单向链表节点
class Node {
    public int value;
    public Node next;

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

// 定义双向链表节点
class DoubleNode {
    public int value;
    public DoubleNode next;
    public DoubleNode last;

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

public class MyList {
    // 生成单向链表
    public static Node buildList(int[] arr) {
        if (arr == null) {
            return null;
        }
        Node head = new Node(arr[0]);
        Node p = head;
        for (int i = 1; i < arr.length; i++) {
            p.next = new Node(arr[i]);
            p = p.next;
        }
        return head;
    }

    // 生成双向链表
    public static DoubleNode buildDoubleList(int[] arr) {
        if (arr == null) {
            return null;
        }
        DoubleNode head = new DoubleNode(arr[0]);
        DoubleNode curDoubleNode = head;
        DoubleNode preDoubleNode = null;
        for (int i = 1; i < arr.length; i++) {
            curDoubleNode.next = new DoubleNode(arr[i]);
            curDoubleNode.last = preDoubleNode;
            preDoubleNode = curDoubleNode;
            curDoubleNode = curDoubleNode.next;
        }
        curDoubleNode.last = preDoubleNode;
        curDoubleNode.next = null;
        return head;
    }

    // 打印单向链表
    public static void printList(Node head) {
        Node p = head;
        while (p.next != null) {
            System.out.print(p.value + "-");
            p = p.next;
        }
        System.out.print(p.value);
        System.out.println();
    }

    // 打印双向链表
    public static void printList(DoubleNode head) {
        DoubleNode p = head;
        DoubleNode pre = null;
        while (p != null) {
            System.out.print(p.value + "-");
            pre = p;
            p = p.next;
        }
        while (pre != null) {
            System.out.print(pre.value + "-");
            pre = pre.last;
        }
        System.out.println();
    }

    // 反转单向链表
    public static Node reverseList(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node nextNode = head.next;
        Node curNode = head;
        Node preNode = null;
        while (true) {
            curNode.next = preNode;
            if (nextNode == null) {
                return curNode;
            }
            preNode = curNode;
            curNode = nextNode;
            nextNode = nextNode.next;
        }
    }

    // 反转双向链表
    public static DoubleNode reverList(DoubleNode head) {
        if (head == null || (head.next == null && head.last == null)) {
            return head;
        }
        DoubleNode curDoubleNode = head;
        DoubleNode preDoubleNode = null;
        DoubleNode nextDoubleNode = head.next;
        while (true) {
            curDoubleNode.next = preDoubleNode;
            curDoubleNode.last = nextDoubleNode;
            if (nextDoubleNode == null) {
                return curDoubleNode;
            }

            preDoubleNode = curDoubleNode;
            curDoubleNode = nextDoubleNode;
            nextDoubleNode = nextDoubleNode.next;
        }
    }
}