在一個合併兩個列表，O（1）時間複雜度

-2

我想問一下如何在C中將兩個未排序列表合併到一個未排序列表中，因爲我們需要一個while循環來獲取所有元素。在一個合併兩個列表，O（1）時間複雜度

例如：

List1: 2 5 1 4 3 
List2: 5 9 4 2 5 7 8 
List3: elements of the two lists,don't care about order

不要評判我，我是初學者。

來源

2014-10-28 programfrog

請說明你是如何實現一個列表。這將幫助其他人提供更好的答案。提供您的代碼的工作示例將有助於進一步。 – 2014-10-28 16:30:21

我真的不明白邏輯adriano ...你能告訴我更多嗎？ – programfrog 2014-10-28 16:31:30

如果我將第一個列表的尾部和第二個列表的尾部作爲參數，並將尾部指向第二個列表的頭部，它會起作用嗎？ – programfrog 2014-10-28 16:40:13

這取決於內存中的數據結構以及是否可以修改現有列表。

如果你可以修改現有的列表，那麼你可以詢問List1它的最後一個元素（這是O（1）是列表頭部有一個指向列表末尾的指針），然後它只是一個問題List1->last->next = List2->head 。之後，遍歷List1將迭代所有元素。

如果您不能更改List1，那麼您必須複製該列表;這對於O（1）來說很棘手，但如果將所有元素保留在單個內存區域（即，不使用指向節點的指針;而是將所有節點保留在數組中），仍然可能。在這種情況下，您爲兩個列表的節點分配內存，然後您可以使用兩次memcopy()填充結果。當然，memcopy()並不是真正的O（1），但是對於當前的CPU（可以每秒複製千兆字節），通常不會注意到差異。

來源

2014-10-28 16:39:36

tl; dr：去閱讀鏈表數據結構。所有這些東西都很常見。

一個真正的O（1）追加的最低要求是你有可變的鏈表和尾部的定時訪問。

所以，一個最簡單的鏈表是：

struct ListNode { 
    struct ListNode *next; 
    int data; /* or void*, or whatever */ 
}; 

typedef struct ListNode *SinglyLinkedList;

即，你只是抱着一個指針到列表中的第一個元素。在這種情況下，尾巴是線性時間（O(n)），所以你不能做你想要的。但是，如果相反，我們使用

struct ListHeadTail { 
    struct ListNode *head; 
    struct ListNode *tail; 
    /* could keep length here as well, if you want it */ 
};

然後插入到列表是稍硬，但你可以輕鬆地做一個固定時間追加：

struct ListHeadTail append(struct ListHeadTail *first, 
          struct ListHeadTail *second) { 
    struct ListHeadTail result; 

    /* special cases first, where either first or second is empty */ 
    if (first->head == NULL) { 
     result = *second; 
     second->head = second->tail = NULL; 
    } else if (second->head == NULL) { 
     result = *first; 
     first->head = first->tail = NULL; 
    } else { 
     result.head = first->head; 
     result.tail = second->tail; 
     first->tail->next = second->head; 
     first->head = first->tail = NULL; 
     second->head = second->tail = NULL; 
    } 
    return result; 
}

其他常見的結構是雙向鏈表 - 再次與一個哨兵節點，而不是有head->prev == tail->next == NULL。

來源

2014-10-28 16:51:35 Useless

我不問你有關列表的問題......我正在談論一個合併它們的函數 – programfrog 2014-10-28 16:54:36

你沒有詳細說明你的意思是什麼。如果你的意思是類似於第二種 - 任何單向鏈接的列表，你可以隨時訪問尾部 - 或者一個循環雙向鏈表等，並且允許你損害你的輸入列表，那麼你的答案是問題是微不足道的。如此微不足道，我假設你對數據結構而不是算法（在可分離的程度上）感到困惑。 – Useless 2014-10-28 16:59:03

我很抱歉，我問了這麼愚蠢的事情......對於你認識的人來說，即使是像我這樣的愚蠢的人也不錯。 – programfrog 2014-10-28 17:02:08

如果你想要的東西行爲作爲一個連接列表，你確實可以通過創建一個由兩個現有List類構造的ConcatenatedList類來實現。如果你正在使用純C而不是C++，那麼類的概念可能需要付出一點努力，但在結構上，這個想法是一樣的。

ConcatenatedList類可以具有兩個屬性：一個頭部屬性，它只不過是對第一個List的引用，另一個是尾部屬性，它只不過是對第二個List的引用。

然後，您可以使用ConcatenatedList模仿基本List類的方法。要訪問ConcatenatedList的第k個元素，嘗試這樣的事：

if (k < header->size()) { return header->getElement(k); } return tail->getElement(k - header->size());

編碼的其餘部分應該是從那裏直接的。

使用這種方法，連接過程將是O（1）。

值得注意的是，通過給出的答案（不）無用也是有效的，但它假定一個LinkedList結構到你的列表，而這種做法並沒有這一要求。然而，有可能在重複連接之後，這種方法將在性能方面看起來像LinkedList實現。

來源

2014-10-28 18:48:27

在一個合併兩個列表，O（1）時間複雜度

回答

相關問題