Проверьте, объединяются ли два связанных списка. Если так, где?

int FindMergeNode(Node headA, Node headB) {
  Node currentA = headA;
  Node currentB = headB;

  // Do till the two nodes are the same
  while (currentA != currentB) {
    // If you reached the end of one list start at the beginning of the other
    // one currentA
    if (currentA.next == null) {
      currentA = headB;
    } else {
      currentA = currentA.next;
    }
    // currentB
    if (currentB.next == null) {
      currentB = headA;
    } else {
      currentB = currentB.next;
    }
  }
  return currentB.data;
}

Я тестировал объединить случай на моем FC9 x86_64 и распечатать каждый адрес узла, как показано ниже:

Head A 0x7fffb2f3c4b0
0x214f010
0x214f030
0x214f050
0x214f070
0x214f090
0x214f0f0
0x214f110
0x214f130
0x214f150
0x214f170


Head B 0x7fffb2f3c4a0
0x214f0b0
0x214f0d0
0x214f0f0
0x214f110
0x214f130
0x214f150
0x214f170

Обратите внимание, потому что я выровнял структуру узла, поэтому, когда malloc () узел, адрес выравнивается по 16 байтам, см. минимум 4 бита . Младшие биты - это 0, то есть 0x0 или 000b. Поэтому, если вы находитесь в том же особом случае (выровненный адрес узла), вы можете использовать эти минимум 4 бита. Например, при перемещении обоих списков от начала до конца установите 1 или 2 из 4 бит адреса посещающего узла, то есть установите флаг;

next_node = node->next;
node = (struct node*)((unsigned long)node | 0x1UL);

Примечание выше флаги не повлияют на реальный адрес узла, а только на ваш СОХРАНЕННЫЙ значение указателя узла.

Если обнаружено, что кто-то установил бит (ы) флага, то первый найденный узел должен быть точкой слияния. после этого вы восстановите адрес узла, очистив установленные вами биты флага. при этом важно соблюдать осторожность при выполнении итерации (например, node = node-> next) для очистки. помните, что вы установили биты флагов, поэтому сделайте так

real_node = (struct node*)((unsigned long)node) & ~0x1UL);
real_node = real_node->next;
node = real_node;

Поскольку это предложение восстановит измененные адреса узлов, его можно рассматривать как «без изменений».

Maybe I am over simplifying this, but simply iterate the smallest list and use the last nodes Link as the merging point?

So, where Data->Link->Link == NULL is the end point, giving Data->Link as the merging point (at the end of the list).

EDIT:

Okay, from the picture you posted, you parse the two lists, the smallest first. With the smallest list you can maintain the references to the following node. Now, when you parse the second list you do a comparison on the reference to find where Reference [i] is the reference at LinkedList[i]->Link. This will give the merge point. Time to explain with pictures (superimpose the values on the picture the OP).

You have a linked list (references shown below):

A->B->C->D->E

You have a second linked list:

1->2->

With the merged list, the references would then go as follows:

1->2->D->E->

Therefore, you map the first "smaller" list (as the merged list, which is what we are counting has a length of 4 and the main list 5)

Loop through the first list, maintain a reference of references.

The list will contain the following references Pointers { 1, 2, D, E }.

We now go through the second list:

-> A - Contains reference in Pointers? No, move on
-> B - Contains reference in Pointers? No, move on
-> C - Contains reference in Pointers? No, move on
-> D - Contains reference in Pointers? Yes, merge point found, break.

Sure, you maintain a new list of pointers, but thats not outside the specification. However the first list is parsed exactly once, and the second list will only be fully parsed if there is no merge point. Otherwise, it will end sooner (at the merge point).

Это, возможно, нарушает условие «анализировать каждый список только один раз», но реализует алгоритм черепахи и зайца (используется для определения точки слияния и длины цикла циклического списка ), поэтому вы начинаете со списка A, и когда вы достигаете NULL в конце, вы делаете вид, что это указатель на начало списка B, тем самым создавая видимость циклического списка. Затем алгоритм сообщит вам, насколько далеко от списка A находится слияние (переменная 'mu' согласно описанию в Википедии).

Кроме того, значение «лямбда» сообщает вам длину списка B, и если вы хотите , вы можете определить длину списка A во время алгоритма (когда вы перенаправляете ссылку NULL).

Here's a solution, computationally quick (iterates each list once) but uses a lot of memory:

for each item in list a
  push pointer to item onto stack_a

for each item in list b
  push pointer to item onto stack_b

while (stack_a top == stack_b top) // where top is the item to be popped next
  pop stack_a
  pop stack_b

// values at the top of each stack are the items prior to the merged item

Ответ Павла требует изменения списков , а также повторения каждого списка дважды.

Вот решение, которое только требует повторения каждого списка дважды (первый раз для вычисления их длины; если длина указана, вам нужно выполнить итерацию только один раз).

Идея состоит в том, чтобы игнорируйте начальные записи более длинного списка (точка слияния не может быть там), чтобы два указателя находились на одинаковом расстоянии от конца списка. Затем переместите их вперед, пока они не сольются.

lenA = count(listA) //iterates list A
lenB = count(listB) //iterates list B

ptrA = listA
ptrB = listB

//now we adjust either ptrA or ptrB so that they are equally far from the end
while(lenA > lenB):
    ptrA = ptrA->next
    lenA--
while(lenB > lenA):
    prtB = ptrB->next
    lenB--

while(ptrA != NULL):
    if (ptrA == ptrB):
        return ptrA //found merge point
    ptrA = ptrA->next
    ptrB = ptrB->next

Это асимптотически то же самое (линейное время), что и мой другой ответ, но, вероятно, имеет меньшие константы, поэтому, вероятно, быстрее. Но я думаю, что мой другой ответ круче.

Хорошо, если вы знаете, что они будут объединены:

Допустим, вы начинаете с:

A-->B-->C
        |
        V
1-->2-->3-->4-->5

1) Просмотрите первый список, устанавливая каждый следующий указатель на NULL.

Теперь вы have:

A   B   C

1-->2-->3   4   5

2) Теперь просмотрите второй список и подождите, пока не увидите NULL, это ваша точка слияния.

Если вы не можете быть уверены, что они сливаются, вы можете использовать контрольное значение для значения указателя , но это не так элегантно.

If we could iterate lists exactly twice, than I can provide method for determining merge point:

• iterate both lists and calculate lengths A and B
• calculate difference of lengths C = |A-B|;
• start iterating both list simultaneously, but make additional C steps on list which was greater
• this two pointers will meet each other in the merging point