题目

实现反转单向链表和双向链表，要求：如果链表长度为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 DoubleNodeReversal {
    public static void main(String[] args) {
        DoubleNode head = new DoubleNode(1);
        // 构建一个双向链表 1 2 3 4
        DoubleNode mid1 = new DoubleNode(2);
        DoubleNode mid2 = new DoubleNode(3);
        DoubleNode tail = new DoubleNode(4);

        head.next = mid1;
        mid1.pre = head;
        mid1.next = mid2;
        mid2.pre = mid1;
        mid2.next = tail;
        tail.pre = mid2;

        System.out.print("Original list: ");
        printList(head);
        
        System.out.print("Reversed list: ");
        DoubleNode reversedHead = reverseList(head);
        printList(reversedHead);
    }

    public static DoubleNode reverseList(DoubleNode head) {
        DoubleNode prev = null;
        DoubleNode current = head;

        while (current != null) {
            DoubleNode nextTemp = current.next;
            current.next = prev;
            prev = current;
            current = nextTemp;
        }

        return prev;
    }

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

关键字

链表，单向，双向，反转

老规矩，代码截图，免得手机上看代码很不爽

● ● ● ● ●