如何連接循環雙向鏈表

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）:)保持小免責聲明 - 不是最好的質量代碼，但你得到的圖片。