algorithm - 如何连接循环双向链表

Question

考虑一下，我已经给出了循环双向链表 A 和 B 的 2 项。我想实现一个连接这两个列表的函数。

这个任务很简单。但是，我想处理 A 和 B 是同一个链表的成员的情况。在这种情况下，它什么都不做。是否可以在 O(1) 中实现它？我需要先检查 A 和 B 是否来自同一个列表吗？或者我能以某种方式神奇地交换/混合指针吗？

IMO 这是不可能的，但我无法证明这一点。

谢谢

Answer 1

可以。出于好奇，我草拟了一个 Java 实现。假设一个链表如下

public class CLinkedList {

    class Node {
        Node prev, next;
        int val;

        public Node(int v) {
            val = v;
        }
    }

    Node s;

    public CLinkedList(Node node) {
        s = node;
    }

    void traverse() {
        if (s == null)
            return;

        Node n = s;
        do {
            System.out.println(n.val);
            n = n.next;
        } while (n != s);
    }
    ...
}

合并方法看起来像

void join(CLinkedList list) {
    Node prev = list.s.prev;
    Node sprev = s.prev;

    prev.next = s;
    sprev.next = list.s;
    s.prev = prev;
    list.s.prev = sprev; 
}

当列表不同时，它工作得很好。

如果不是，所有这一切只是将原始列表拆分为两个完全有效的不同链表。你所要做的就是再次加入他们。

编辑:join 方法连接(笑)两个不同的列表，或者(与其名称相反)如果节点属于同一列表则拆分列表.因此，应用 join 两次实际上没有任何效果。但是您可以通过其他方式使用此属性。下面的方法工作正常:

public void merge(CLinkedList list) {
    CLinkedList nList = new CLinkedList(s.next);
    join(nList);
    nList.join(list);
    join(nList);
}

public static void main(String[] args) {
    CLinkedList list = new CLinkedList(new int[] {1,2,3});
    CLinkedList nlist = new CLinkedList(list.s.next);
    list.merge(nlist);
    list.traverse();
}

仍然是 O(1) :) 保留小的免责声明 - 不是最好质量的代码，但你明白了。