算法 - 链表

链表

问题一：反转单向和双向链表

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

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

反转单向链表

public static Node reverseOne(Node head) {
    if (head == null || head.next == null) {
        return head;
    }
    Node new_head = null;
    while (head != null) {
        Node tmp = head.next;
        head.next = new_head;
        new_head = head;
        head = tmp;
    }
    return new_head;
}

public static Node reverseTwo(Node head) {
    if (head == null || head.next == null) {
        return head;
    }
    Node pre = null;
    Node next = null;
    while (head != null) {
        next = head.next;
        head.next = pre;
        pre = head;
        head = next;
    }
    return pre;
}

反转双向链表

public static DoubleNode reverse(DoubleNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    DoubleNode pre = null;
    DoubleNode next = null;
    while (head != null) {
        next = head.next;
        head.next = pre;
        head.last = next;
        pre = head;
        head = next;
    }
    return pre;
}