反转单向和双向链表

【题目】 分别实现反转单向链表和反转双向链表的函数。 

【要求】 如果链表长度为 N，时间复杂度要求为 O(N)，额外空间复杂度要求为 O(1)。

public class ReverseList {

    class Node {
        private int value;
        private Node next;

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

    class DoubleNode {
        private int value;
        private DoubleNode next;
        private DoubleNode last;

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

    /**
     * 反转单链表
     * @param head
     * @return
     */
    public Node reverseList(Node head) {
        // pre代指当前节点的前一个节点
        Node pre = null;
        // next代指当前节点的后一个节点
        Node next = null;
        // cur代指当前节点
        Node cur = head;

        // 当前节点不为空
        while (cur != null) {
            // next指向当前节点的后一个节点
            next = cur.next;

            // 当前节点反转指针，把指针指向前一个节点
            cur.next = pre;

            // 反转后pre当前节点前一个节点向后移
            pre = cur;
            // cur当前节点向后移
            cur = next;
        }

        // 循环走完之后，cur指向空，pre指向了反转后的头节点
        return pre;
    }

    /**
     * 反转双向链表
     * @param head
     * @return
     */
    public DoubleNode reverseList(DoubleNode head) {
        // pre代指当前节点的前一个节点
        DoubleNode pre = null;
        // next代指当前节点的后一个节点
        DoubleNode next = null;
        // cur指向当前节点
        DoubleNode cur = head;

        while (cur != null) {
            // 使next 指向当前节点的后一个节点
            next = cur.next;

            // 反转节点指向
            // 当前节点的next指针指向当前节点的前一个节点
            cur.next = pre;
            // 当前节点的last指针指向当前节点的后一个节点
            cur.last = next;

            pre = cur;
            cur = next;
        }
        return pre;
    }
    
}