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

Этот вопрос может быть старым, но я не мог придумать ответа.

Скажем, есть два списка разной длины, сливающиеся в одной точке ; как мы узнаем, где находится точка слияния?

Условия:

1. Мы не знаем длины
2. Мы должны анализировать каждый список только один раз.

Если

• под "модификация не разрешена" имелось в виду "вы можете изменить, но в конце концов они должны быть восстановлены", и
• мы могли перебирать списки ровно дважды

следующий алгоритм был бы решением.

Во-первых, цифры. Предположим, что первый список имеет длину, a+cа второй - длину b+c, где c- длина их общего «хвоста» (после точки слияния). Обозначим их так:

x = a+c
y = b+c

Так как мы не знаем длины, будем рассчитывать xи yбез дополнительных итераций; вы увидите как.

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

После этого, когда другой итератор достигнет точки слияния, он не перейдет к общему хвосту. Вместо этого вернется к прежнему началу списка, который до этого достигал точки слияния! Таким образом, прежде чем он достигнет конца измененного списка (то есть бывшего начала другого списка), он выполнит a+b+1общее количество итераций. Назовем это z+1.

Указатель, который первым достиг точки слияния, будет продолжать повторяться, пока не достигнет конца списка. Количество сделанных итераций должно быть рассчитано и равно x.

Затем этот указатель выполняет итерацию назад и снова меняет списки. Но теперь он не вернется в начало списка, с которого изначально начинал! Вместо этого он перейдет в начало другого списка! Количество сделанных итераций должно быть рассчитано и равно y.

Итак, нам известны следующие числа:

x = a+c
y = b+c
z = a+b

Из чего определяем, что

a = (+x-y+z)/2
b = (-x+y+z)/2
c = (+x+y-z)/2

Что решает проблему.

Следующее, безусловно, лучшее из всего, что я видел - O (N), без счетчиков. Я получил его во время собеседования с кандидатом в SN в VisionMap .

Сделайте такой интерактивный указатель: он каждый раз продвигается вперед до конца, а затем переходит в начало противоположного списка и так далее. Создайте два из них, указывая на две головы. Передвигайте каждый из указателей на 1 каждый раз, пока они не встретятся. Это произойдет после одного или двух проходов.

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

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

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

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

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.

Теперь у вас есть:

A   B   C

1-->2-->3   4   5

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

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

Если бы мы могли повторять списки ровно дважды, тогда я мог бы предоставить метод для определения точки слияния:

• перебрать оба списка и вычислить длины A и B
• вычислить разность длин C = | AB |;
• начать повторение обоих списков одновременно, но сделать дополнительные шаги C в списке, который был больше
• эти два указателя встретятся друг с другом в точке слияния

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

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

Вы можете использовать набор узлов. Просмотрите один список и добавьте каждый узел в набор. Затем выполните итерацию по второму списку и для каждой итерации проверьте, существует ли узел в наборе. Если да, то вы нашли свою точку слияния :)

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

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

Может быть, я слишком упрощаю это, а просто перебираю наименьший список и использую последние узлы Linkкак точку слияния?

Итак, где Data->Link->Link == NULLнаходится конечная точка, указывается Data->Linkкак точка слияния (в конце списка).

РЕДАКТИРОВАТЬ:

Хорошо, судя по опубликованной вами картинке, вы разбираете два списка, сначала самый маленький. С наименьшим списком вы можете поддерживать ссылки на следующий узел. Теперь, когда вы анализируете второй список, вы сравниваете ссылку, чтобы найти, где Reference [i] является ссылкой в ​​LinkedList [i] -> Link. Это даст точку слияния. Пора объяснять картинками (наложите значения на картинку ОП).

У вас есть связанный список (ссылки показаны ниже):

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

У вас есть второй связанный список:

1->2->

В объединенном списке ссылки будут выглядеть следующим образом:

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

Поэтому вы сопоставляете первый «меньший» список (поскольку объединенный список, который мы считаем, имеет длину 4, а основной список 5)

Прокрутите первый список, сохраните ссылку на ссылки.

Список будет содержать следующие ссылки Pointers { 1, 2, D, E }.

Теперь пройдемся по второму списку:

-> 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.

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

Я протестировал случай слияния на моем 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;

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

Может быть простое решение, но для этого потребуется дополнительное пространство. Идея состоит в том, чтобы пройти по списку и сохранить каждый адрес в хэш-карте, а теперь пройти по другому списку и сопоставить, находится ли адрес в хэш-карте или нет. Каждый список просматривается только один раз. Никаких изменений в списках нет. Длина пока неизвестна. Используемое вспомогательное пространство: O (n), где n - длина первого пройденного списка.

это решение выполняет итерацию каждого списка только один раз ... никаких изменений списка тоже не требуется ... хотя вы можете жаловаться на пространство ..
1) В основном вы выполняете итерацию в list1 и сохраняете адрес каждого узла в массиве (который хранит значение unsigned int)
2) Затем вы выполняете итерацию list2, и для каждого адреса узла ---> вы просматриваете массив, который вы найдете совпадение или нет ... если вы это сделаете, то это будет узел слияния

//pseudocode
//for the first list
p1=list1;
unsigned int addr[];//to store addresses
i=0;
while(p1!=null){
  addr[i]=&p1;
  p1=p1->next;
}
int len=sizeof(addr)/sizeof(int);//calculates length of array addr
//for the second list
p2=list2;
while(p2!=null){
  if(search(addr[],len,&p2)==1)//match found
  {
    //this is the merging node
    return (p2);
  }
  p2=p2->next;
}

int search(addr,len,p2){
  i=0;  
  while(i<len){
    if(addr[i]==p2)
      return 1;
    i++;
  }
 return 0;
} 

Надеюсь, это верное решение ...

Нет необходимости изменять какой-либо список. Есть решение, в котором нам нужно пройти по каждому списку только один раз.

1. Создайте два стека, скажем, stck1 и stck2.
2. Пройдите по 1-му списку и нажмите копию каждого узла, который вы проходите в stck1.
3. То же, что и в шаге два, но на этот раз пройдитесь по 2-му списку и отправьте копию узлов в stck2.
4. Теперь извлеките из обоих стеков и проверьте, равны ли два узла, если да, то сохраните ссылку на них. Если нет, то предыдущие равные узлы на самом деле являются той точкой слияния, которую мы искали.

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 = headA;
    } else {
      currentA = currentA.next;
    }
    // currentB
    if (currentB.next == null) {
      currentB = headB;
    } else {
      currentB = currentB.next;
    }
  }
  return currentB.data;
}

Вот наивное решение, не нужно просматривать целые списки.

если ваш структурированный узел имеет три поля, например

struct node {
    int data;   
    int flag;  //initially set the flag to zero  for all nodes
    struct node *next;
};

скажем, у вас есть две головы (head1 и head2), указывающие на начало двух списков.

Просмотрите оба списка с одинаковой скоростью и установите флаг = 1 (флаг посещенных) для этого узла,

  if (node->next->field==1)//possibly longer list will have this opportunity
      //this will be your required node. 

Как насчет этого:

1. Если вам разрешено проходить каждый список только один раз, вы можете создать новый узел, пройти по первому списку, чтобы каждый узел указывал на этот новый узел, и пройти по второму списку, чтобы увидеть, указывает ли какой-либо узел на ваш новый узел ( это ваша точка слияния). Если второй обход не приводит к вашему новому узлу, то исходные списки не имеют точки слияния.

2. Если вам разрешено перемещаться по спискам более одного раза, вы можете пройти по каждому списку, чтобы найти их длину, и если они различаются, опустите «лишние» узлы в начале более длинного списка. Затем просто просмотрите оба списка по одному шагу за раз и найдите первый узел слияния.

Шаги в Java:

1. Создайте карту.
2. Начните обход в обеих ветвях списка и поместите все пройденные узлы списка на карту, используя какую-то уникальную вещь, связанную с узлами (например, идентификатор узла) в качестве ключа, и поместите значения как 1 в начало для всех.
3. Когда появляется первый дублирующийся ключ, увеличивайте значение этого ключа (скажем, теперь его значение стало 2, что> 1.
4. Получите ключ, значение которого больше 1, и это должен быть узел, в котором два списка объединяются.

Мы можем эффективно решить эту проблему, введя поле isVisited. Просмотрите первый список и установите значение "isVisited" равным "true" для всех узлов до конца. Теперь начните со второго и найдите первый узел, где флаг истинен, а Boom - это ваша точка слияния.

Шаг 1: найдите длину обоих списков Шаг 2: Найдите разницу и переместите самый большой список с разницей Шаг 3: Теперь оба списка будут в аналогичном положении. Шаг 4. Просмотрите список, чтобы найти точку слияния

//Psuedocode
def findmergepoint(list1, list2):
lendiff = list1.length() > list2.length() : list1.length() - list2.length() ? list2.lenght()-list1.lenght()
biggerlist = list1.length() > list2.length() : list1 ? list2  # list with biggest length
smallerlist = list1.length() < list2.length() : list2 ? list1 # list with smallest length


# move the biggest length to the diff position to level both the list at the same position
for i in range(0,lendiff-1):
    biggerlist = biggerlist.next
#Looped only once.  
while ( biggerlist is not None and smallerlist is not None ):
    if biggerlist == smallerlist :
        return biggerlist #point of intersection


return None // No intersection found

int FindMergeNode(Node *headA, Node *headB)
{
    Node *tempB=new Node;
    tempB=headB;
   while(headA->next!=NULL)
       {
       while(tempB->next!=NULL)
           {
           if(tempB==headA)
               return tempB->data;
           tempB=tempB->next;
       }
       headA=headA->next;
       tempB=headB;
   }
    return headA->data;
}

Используйте карту или словарь, чтобы сохранить адрес и значение узла. если адрес уже существует в карте / словаре, то ответом является значение ключа. Я сделал это:

int FindMergeNode(Node headA, Node headB) {

Map<Object, Integer> map = new HashMap<Object, Integer>();

while(headA != null || headB != null)
{
    if(headA != null && map.containsKey(headA.next))
    {
        return map.get(headA.next);
    }

    if(headA != null && headA.next != null)
    {
         map.put(headA.next, headA.next.data);
         headA = headA.next;
    }

    if(headB != null && map.containsKey(headB.next))
    {
        return map.get(headB.next);
    }

    if(headB != null && headB.next != null)
    {
        map.put(headB.next, headB.next.data);
        headB = headB.next;
    }
}

return 0;
}

Решение сложности АО (п). Но исходя из предположения.

предположение: оба узла имеют только положительные целые числа.

логика: сделать все целое число list1 отрицательным. Затем пройдите по списку 2, пока не получите отрицательное целое число. Найдя => возьми, снова поменяй знак на положительный и возвращайся.

static int findMergeNode(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {

    SinglyLinkedListNode current = head1; //head1 is give to be not null.

    //mark all head1 nodes as negative
    while(true){
        current.data = -current.data;
        current = current.next;
        if(current==null) break;
    }

    current=head2; //given as not null
    while(true){
        if(current.data<0) return -current.data;
        current = current.next;
    }

}

Мы можем использовать два указателя и перемещаться таким образом, чтобы, если один из указателей имеет значение NULL, мы указываем его на заголовок другого списка и то же самое для другого, таким образом, если длины списков различаются, они встретятся во втором проходе. . Если длина list1 равна n, а list2 равна m, их разница составляет d = abs (nm). Они преодолеют это расстояние и встретятся в точке слияния.
Код:

int findMergeNode(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {
    SinglyLinkedListNode* start1=head1;
    SinglyLinkedListNode* start2=head2;
    while (start1!=start2){
        start1=start1->next;
        start2=start2->next;
        if (!start1)
        start1=head2;
        if (!start2)
        start2=head1;
    }
    return start1->data;
}

Вы можете добавить узлы list1в хэш-набор и цикл через второй, и если какой-либо узел list2уже присутствует в наборе. Если да, то это узел слияния

static int findMergeNode(SinglyLinkedListNode head1, SinglyLinkedListNode head2) {
    HashSet<SinglyLinkedListNode> set=new HashSet<SinglyLinkedListNode>();
    while(head1!=null)
    {
        set.add(head1);
        head1=head1.next;
    }
    while(head2!=null){
        if(set.contains(head2){
            return head2.data;
        }
    }
    return -1;
}

Решение с использованием javascript

var getIntersectionNode = function(headA, headB) {
    
    if(headA == null || headB == null) return null;
    
    let countA = listCount(headA);
    let countB = listCount(headB);
    
    let diff = 0;
    if(countA > countB) {

        diff = countA - countB;
        for(let i = 0; i < diff; i++) {
            headA = headA.next;
        }
    } else if(countA < countB) {
        diff = countB - countA;
        for(let i = 0; i < diff; i++) {
            headB = headB.next;
        }
    }

    return getIntersectValue(headA, headB);
};

function listCount(head) {
    let count = 0;
    while(head) {
        count++;
        head = head.next;
    }
    return count;
}

function getIntersectValue(headA, headB) {
    while(headA && headB) {
        if(headA === headB) {
            return headA;
        }
        headA = headA.next;
        headB = headB.next;
    }
    return null;
}

Если разрешено редактирование связанного списка,

1. Затем просто сделайте указатели следующих узлов всех узлов списка 2 нулевыми.
2. Найдите значение данных последнего узла списка 1. Это даст вам пересекающийся узел при однократном обходе обоих списков без «логики Hi-Fi».