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

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

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

Условия:

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

Пример двух объединенных связанных списков.

80 голосов | спросил rplusg 20 +04002009-10-20T15:51:10+04:00312009bEurope/MoscowTue, 20 Oct 2009 15:51:10 +0400 2009, 15:51:10

20 ответов


0

Если

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

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

Во-первых, цифры. Предположим, что первый список имеет длину 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

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

ответил P Shved 20 +04002009-10-20T16:47:48+04:00312009bEurope/MoscowTue, 20 Oct 2009 16:47:48 +0400 2009, 16:47:48
0

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

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

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

ответил Pavel Radzivilovsky 19 FebruaryEurope/MoscowbTue, 19 Feb 2013 15:16:38 +0400000000pmTue, 19 Feb 2013 15:16:38 +040013 2013, 15:16:38
0

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

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

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

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

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

ответил Artelius 21 +04002009-10-21T02:16:57+04:00312009bEurope/MoscowWed, 21 Oct 2009 02:16:57 +0400 2009, 02:16:57
0

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

  • итерируйте оба списка и вычисляйте длины A и B
  • вычислить разницу длин C = | A-B |;
  • начните повторять оба списка одновременно, но сделайте дополнительные шаги C в списке, который был больше
  • эти два указателя встретятся в точке слияния
ответил rachvela 26 +03002009-10-26T20:09:59+03:00312009bEurope/MoscowMon, 26 Oct 2009 20:09:59 +0300 2009, 20:09:59
0

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

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
ответил Skizz 20 +04002009-10-20T17:12:09+04:00312009bEurope/MoscowTue, 20 Oct 2009 17:12:09 +0400 2009, 17:12:09
0

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

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

ответил Artelius 20 +04002009-10-20T16:11:57+04:00312009bEurope/MoscowTue, 20 Oct 2009 16:11:57 +0400 2009, 16:11:57
0

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

ответил isyi 8 FebruaryEurope/MoscowbFri, 08 Feb 2013 11:14:21 +0400000000amFri, 08 Feb 2013 11:14:21 +040013 2013, 11:14:21
0

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

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

EDIT:

Хорошо, из картинки, которую вы разместили, вы анализируете два списка, самый маленький в первую очередь. С наименьшим списком вы можете поддерживать ссылки на следующий узел. Теперь, когда вы анализируете второй список, вы сравниваете ссылку, чтобы найти, где 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.

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

ответил Kyle Rozendo 20 +04002009-10-20T15:53:38+04:00312009bEurope/MoscowTue, 20 Oct 2009 15:53:38 +0400 2009, 15:53:38
0

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

Обратите внимание, что флаги выше не влияют на реальный адрес узла, а только на значение указателя SAVED узла.

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

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

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

ответил Test 20 +04002009-10-20T19:54:31+04:00312009bEurope/MoscowTue, 20 Oct 2009 19:54:31 +0400 2009, 19:54:31
0

это решение повторяет каждый список только один раз ... изменение списка также не требуется .. хотя вы можете жаловаться на пробел ..
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;
} 

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

ответил rajya vardhan 7 MarpmMon, 07 Mar 2011 21:53:27 +03002011-03-07T21:53:27+03:0009 2011, 21:53:27
0

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

  1. Создайте два стека, скажем, stck1 и stck2.
  2. Пройдите по 1-му списку и нажмите копию каждого узла, по которому вы проходите, в stck1.
  3. То же, что и на втором шаге, но на этот раз просмотрите второй список и отправьте копию узлов в stck2.
  4. Теперь извлеките из обоих стеков и проверьте, равны ли два узла, если да, то сохраните ссылку на них. Если нет, то предыдущие узлы, которые были равны, фактически являются точкой слияния, которую мы искали.
ответил ABVash 9 J0000006Europe/Moscow 2018, 16:49:04
0

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

ответил Vikas Agarwal 5 AM00000080000005331 2018, 08:31:53
0

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

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

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. 
ответил Anil Kumar Arya 27 FebruaryEurope/MoscowbMon, 27 Feb 2012 12:37:33 +0400000000pmMon, 27 Feb 2012 12:37:33 +040012 2012, 12:37:33
0

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

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

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

ответил user2024069 30 Jam1000000amWed, 30 Jan 2013 09:19:53 +040013 2013, 09:19:53
0

Шаги в Java:

  1. Создайте карту.
  2. Начните обход в обеих ветвях списка и поместите все пройденные узлы списка в карту, используя некоторую уникальную вещь, связанную с узлами (скажем, идентификатор узла), в качестве ключа и установите значения как 1 в начале для всех.
  3. Когда появляется первый дубликат ключа, увеличивайте значение этого ключа (скажем, теперь его значение стало 2, что равно> 1.
  4. Получите ключ, значение которого больше 1, и это должен быть узел, где объединяются два списка.
ответил King KB 28 AMpSun, 28 Apr 2013 11:36:25 +040036Sunday 2013, 11:36:25
0

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

ответил Riya kathil 17 +03002016-10-17T21:23:59+03:00312016bEurope/MoscowMon, 17 Oct 2016 21:23:59 +0300 2016, 21:23:59
0

Шаг 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
ответил svaithin 14 12016vEurope/Moscow11bEurope/MoscowMon, 14 Nov 2016 14:52:00 +0300 2016, 14:52:00
0
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;
}
ответил Yachana Yachana 16 Mayam17 2017, 10:05:00
0

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

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;
}
ответил Vishal Anand 29 J0000006Europe/Moscow 2017, 04:24:59
0

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

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

Логика

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

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;
    }

}
ответил user3828943 28 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowFri, 28 Sep 2018 22:08:15 +0300 2018, 22:08:15

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132