O(1)可逆双向链表的O(1)合并问题求助

核心问题在于你只依赖底层链表的物理结构，没有维护用户视角下的逻辑首尾节点。只要给每个链表对象新增两个指针（逻辑首front、逻辑尾back），配合已有的反转标记is_reversed，就能轻松实现O(1)合并，不管两个链表是否处于反转状态。

调整链表结构 #

每个链表对象维护三个核心属性：

• is_reversed: bool，标记当前是否处于反转状态
• front: Node*，用户视角下的链表首节点
• back: Node*，用户视角下的链表尾节点

反转操作依然保持O(1)：只需交换front和back，翻转is_reversed即可，完全不需要修改底层节点的指针。

O(1)合并的具体操作 #

假设要合并链表L1和L2，得到用户视角下L1的逻辑顺序 + L2的逻辑顺序的新链表，步骤如下：

1. 确定连接点：取L1的逻辑尾L1.back，L2的逻辑首L2.front。
2. 双向连接两个节点：根据两个链表的反转状态，修改对应物理指针：
   • 对于L1的逻辑尾L1.back：
     • 如果L1是反转状态（is_reversed=true），用户调用next()时实际取节点的prev指针，因此将L1.back.prev指向L2.front
     • 如果L1未反转（is_reversed=false），用户调用next()取节点的next指针，因此将L1.back.next指向L2.front
   • 对于L2的逻辑首L2.front：
     • 如果L2是反转状态（is_reversed=true），用户调用prev()时实际取节点的next指针，因此将L2.front.next指向L1.back
     • 如果L2未反转（is_reversed=false），用户调用prev()取节点的prev指针，因此将L2.front.prev指向L1.back
3. 生成合并后的链表：新链表的front设为L1.front，back设为L2.back，is_reversed初始设为false（后续反转时直接交换首尾即可）。

你的示例验证 #

比如L1是1-2-3（物理结构），反转后is_reversed=true，front=3，back=1；L2是4-5-6（物理结构），未反转is_reversed=false，front=4，back=6。

合并操作：

• L1是反转状态，所以L1.back.prev = L2.front → 1.prev = 4
• L2未反转，所以L2.front.prev = L1.back → 4.prev = 1

用户遍历合并后的链表：

• 从3调用next()：因为L1反转，取3.prev=2 → 再next()取2.prev=1 → 再next()取1.prev=4；进入L2后，未反转，取4.next=5 → 5.next=6，正好是3→2→1→4→5→6，符合预期。
• 从6调用prev()：L2未反转，取6.prev=5 → 5.prev=4 → 4.prev=1；进入L1后，反转状态，取1.next=2 → 2.next=3，得到6→5→4→1→2→3，逻辑正确。

伪代码实现 #

struct Node {
    int val;
    Node* prev;
    Node* next;
};

struct LinkedList {
    bool is_reversed;
    Node* front;
    Node* back;

    // 反转操作
    void reverse() {
        swap(front, back);
        is_reversed = !is_reversed;
    }

    // 合并两个链表，返回新链表
    static LinkedList merge(const LinkedList& l1, const LinkedList& l2) {
        LinkedList merged;
        merged.front = l1.front;
        merged.back = l2.back;
        merged.is_reversed = false;

        // 连接l1.back到l2.front
        if (l1.is_reversed) {
            l1.back->prev = l2.front;
        } else {
            l1.back->next = l2.front;
        }

        // 连接l2.front到l1.back
        if (l2.is_reversed) {
            l2.front->next = l1.back;
        } else {
            l2.front->prev = l1.back;
        }

        return merged;
    }
};

注意：合并后原链表L1、L2不应再被单独操作，避免指针混乱，这属于工程实现上的边界处理，不影响O(1)的时间复杂度。

内容的提问来源于stack exchange，提问作者Scoopy