c - C中的合并链表

Question

我在采访中被问到这个问题:有两个链表的两个表头。c中有一个合并链表，其中第二个链表在某个时候合并到第一个链表中。我们如何确定合并点，找到该点的复杂性如何？

有人可以帮忙吗？

Answer 1

O(n)

search = list1->header;
if (mixed->header == list1->header) search = list2->header;

while (mixed->next != search) mixed = mixed->next;

---

编辑:变量的新名称和一些注释

/* search is what we want to find. Here it's the head of `list2` */
search = list2->header;
/* unless the merging put `list2` first; then we want to search for `list1` */
if (mixed->header == list2->header) search = list1->header;

/* assume (wrongly) that the header for the mixed list is the merge point */
mergepoint = mixed->head;

/* traverse the mixed list until we find the pointer we're searching */
while (mergepoint->next != search) mergepoint = mergepoint->next;
/* mergepoint now points to the merge point */