单双向链表反转【面试题】

题目

实现反转单向链表和双向链表，要求：如果链表长度为N，时间复杂度为O(N)，额外空间复杂度为O(1)

参考答案

图形表示

单向链表

单向反转请参考
双向链表

反转前：头节点的前驱是null，尾节点的后继是null。

反转后：以前的头节点的后继是null，以前的尾节点的前驱是null

java代码实现如下：

//双向链表节点
public class DoubleNode {
    public int value;
    //前驱
    public DoubleNode pre;
    //后继
    public DoubleNode next;

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

public class DoubleLinkedList {
    private DoubleNode head;

    public void append(int value) {
        if (head == null) {
            head = new DoubleNode(value);
            return;
        }

        DoubleNode current = head;
        while (current.next != null) {
            current = current.next;
        }
        current.next = new DoubleNode(value);
        current.next.pre = current;
    }

    public void reverse() {
        if (head == null || head.next == null) {
            return;
        }

        DoubleNode current = head;
        while (current != null) {
            DoubleNode temp = current.next;
            current.next = current.pre;
            current.pre = temp;
            current = temp;
        }
        head = head.pre;
    }

    public void print() {
        DoubleNode current = head;
        while (current != null) {
            System.out.print(current.value + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        DoubleLinkedList list = new DoubleLinkedList();
        list.append(1);
        list.append(2);
        list.append(3);

        System.out.println("Original List:");
        list.print();

        list.reverse();

        System.out.println("Reversed List:");
        list.print();
    }
}

关键字

链表，单向，双向，反转