在一个合并两个列表，O（1）时间复杂度

Question

我想问一下如何在C中将两个未排序列表合并到一个未排序列表中，因为我们需要一个while循环来获取所有元素。

例如：

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 

不要评判我，我是初学者。

Answer 1

这取决于内存中的数据结构以及是否可以修改现有列表。

如果你可以修改现有的列表，那么你可以询问List1它的最后一个元素（这是O（1）是列表头部有一个指向列表末尾的指针），然后它只是一个问题List1->last->next = List2->head 。之后，遍历List1将迭代所有元素。

如果您不能更改List1，那么您必须复制该列表;这对于O（1）来说很棘手，但如果将所有元素保留在单个内存区域（即，不使用指向节点的指针;而是将所有节点保留在数组中），仍然可能。在这种情况下，您为两个列表的节点分配内存，然后您可以使用两次memcopy()填充结果。当然，memcopy()并不是真正的O（1），但是对于当前的CPU（可以每秒复制千兆字节），通常不会注意到差异。

Answer 2

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。

Answer 3

如果你想要的东西行为作为一个连接列表，你确实可以通过创建一个由两个现有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实现。