如何连接循环双向链表

Question

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

这个任务很简单。但是，我想处理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）:)保持小免责声明 - 不是最好的质量代码，但你得到的图片。