Sprawdź, czy dwie połączone listy łączą się. Jeśli tak, to gdzie?

To pytanie może być stare, ale nie mogłem wymyślić odpowiedzi.

Powiedzmy, że istnieją dwie listy o różnych długościach, łączące się w punkcie ; skąd wiemy, gdzie jest punkt łączenia?

Warunki:

1. Nie znamy długości
2. Każdą listę powinniśmy analizować tylko raz.

Jeśli

• przez „modyfikacja jest niedozwolona” oznaczało to „możesz zmienić, ale na koniec należy je przywrócić” i
• moglibyśmy powtórzyć listy dokładnie dwa razy

Rozwiązaniem byłby następujący algorytm.

Najpierw liczby. Załóżmy, że pierwsza lista ma długość, a+ca druga długość b+c, gdzie cjest długością ich wspólnego „ogona” (za punktem połączenia). Oznaczmy je następująco:

x = a+c
y = b+c

Ponieważ nie znamy długości, obliczymy xi ybez dodatkowych iteracji; zobaczysz jak.

Następnie iterujemy każdą listę i odwracamy je podczas iteracji! Jeśli oba iteratory osiągną punkt scalenia w tym samym czasie, to dowiadujemy się tego przez zwykłe porównanie. W przeciwnym razie jeden wskaźnik osiągnie punkt scalenia przed drugim.

Po tym, gdy drugi iterator osiągnie punkt scalenia, nie przejdzie do wspólnego ogona. Zamiast tego wróci do poprzedniego początku listy, która wcześniej osiągnęła punkt scalenia! Tak więc, zanim osiągnie koniec zmienionej listy (tj. Poprzedni początek drugiej listy), dokona a+b+1sumowania iteracji. Nazwijmy to z+1.

Wskaźnik, który jako pierwszy osiągnął punkt scalenia, będzie kontynuował iterację, aż osiągnie koniec listy. Liczba wykonanych iteracji powinna zostać obliczona i jest równa x.

Następnie ten wskaźnik wykonuje iterację wstecz i ponownie odwraca listy. Ale teraz nie wróci do początku listy, z której pierwotnie się rozpoczął! Zamiast tego przejdzie na początek drugiej listy! Liczba wykonanych iteracji powinna być obliczona i równa y.

Znamy więc następujące liczby:

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

Z którego to ustalamy

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

Co rozwiązuje problem.

Oto zdecydowanie największe ze wszystkich, jakie widziałem - O (N), bez liczników. Zdobyłem go podczas rozmowy kwalifikacyjnej z kandydatem na SN w VisionMap .

Utwórz wskaźnik pośredni w ten sposób: przesuwa się do przodu za każdym razem do końca, a następnie przeskakuje na początek przeciwnej listy i tak dalej. Utwórz dwa z nich, wskazując na dwie głowy. Za każdym razem przesuń każdy ze wskaźników o 1, aż się spotkają. Stanie się to po jednym lub dwóch przejściach.

Nadal używam tego pytania w wywiadach - ale żeby zobaczyć, ile czasu zajmuje komuś zrozumienie, dlaczego to rozwiązanie działa.

Odpowiedź Pawła wymaga modyfikacji list, a także dwukrotnego powtórzenia każdej z nich.

Oto rozwiązanie, które wymaga tylko dwukrotnego powtórzenia każdej listy (za pierwszym razem, aby obliczyć ich długość; jeśli podano długość, wystarczy powtórzyć tylko raz).

Chodzi o to, aby zignorować początkowe wpisy dłuższej listy (nie może tam być punktu scalającego), tak aby dwa wskaźniki znajdowały się w równej odległości od końca listy. Następnie przesuń je do przodu, aż się połączą.

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

Jest to asymptotycznie to samo (czas liniowy), co moja inna odpowiedź, ale prawdopodobnie ma mniejsze stałe, więc prawdopodobnie jest szybsze. Ale myślę, że moja druga odpowiedź jest fajniejsza.

Cóż, jeśli wiesz, że się połączą:

Powiedzmy, że zaczynasz od:

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

1) Przejdź przez pierwszą listę, ustawiając każdy następny wskaźnik na NULL.

Teraz masz:

A   B   C

1-->2-->3   4   5

2) Teraz przejrzyj drugą listę i poczekaj, aż zobaczysz NULL, czyli twój punkt łączenia.

Jeśli nie możesz być pewien, że się scalą, możesz użyć wartości wartowniczej dla wartości wskaźnika, ale nie jest to tak eleganckie.

Gdybyśmy mogli iterować listy dokładnie dwa razy, to mogę podać metodę określania punktu scalania:

• iteruj obie listy i oblicz długości A i B.
• obliczyć różnicę długości C = | AB |;
• rozpocznij iterację obu list jednocześnie, ale wykonaj dodatkowe kroki C na liście, która była większa
• te dwa wskaźniki spotkają się w punkcie łączenia

Oto rozwiązanie, szybkie obliczeniowo (raz iteruje każdą listę), ale zużywa dużo pamięci:

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

Możesz użyć zestawu węzłów. Przejdź przez jedną listę i dodaj każdy węzeł do zestawu. Następnie iteruj przez drugą listę i dla każdej iteracji sprawdź, czy węzeł istnieje w zestawie. Jeśli tak, to znalazłeś swój punkt scalania :)

To prawdopodobnie narusza warunek „przeanalizuj każdą listę tylko raz”, ale zaimplementuj algorytm żółwia i zająca (używany do znajdowania punktu scalenia i długości cyklu listy cyklicznej), więc zaczynasz od listy A, a gdy osiągniesz NULL w koniec udajesz, że jest to wskaźnik do początku listy B, tworząc w ten sposób wygląd listy cyklicznej. Algorytm powie Ci wtedy dokładnie, jak daleko w dół listy A znajduje się scalanie (zmienna „mu” zgodnie z opisem w Wikipedii).

Ponadto wartość „lambda” mówi ci o długości listy B, a jeśli chcesz, możesz obliczyć długość listy A podczas wykonywania algorytmu (gdy przekierowujesz łącze NULL).

Może zbytnio to upraszczam, ale po prostu powtarzam najmniejszą listę i używam ostatnich węzłów Linkjako punktu scalania?

Tak więc, gdzie Data->Link->Link == NULLjest punktem końcowym, podając Data->Linkjako punkt łączenia (na końcu listy).

EDYTOWAĆ:

OK, z opublikowanego zdjęcia analizujesz dwie listy, najpierw najmniejszą. Przy najmniejszej liście możesz zachować odniesienia do następnego węzła. Teraz, kiedy analizujesz drugą listę, wykonujesz porównanie referencji, aby znaleźć referencję [i] w LinkedList [i] -> Link. To da punkt scalenia. Czas wyjaśnić zdjęciami (nałożyć wartości na obraz PO).

Masz połączoną listę (referencje pokazane poniżej):

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

Masz drugą połączoną listę:

1->2->

Po połączeniu listy odwołania wyglądałyby następująco:

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

Dlatego mapujesz pierwszą „mniejszą” listę (ponieważ lista połączona, czyli to, co liczymy, ma długość 4, a lista główna 5)

Przejrzyj pierwszą listę, zachowaj referencje referencji.

Lista będzie zawierać następujące odniesienia Pointers { 1, 2, D, E }.

Teraz przejdziemy przez drugą 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.

Jasne, utrzymujesz nową listę wskaźników, ale to nie jest poza specyfikacją. Jednak pierwsza lista jest analizowana dokładnie raz, a druga lista zostanie w pełni przeanalizowana tylko wtedy, gdy nie ma punktu scalania. W przeciwnym razie zakończy się wcześniej (w punkcie scalenia).

Przetestowałem przypadek scalania na moim FC9 x86_64 i wydrukowałem każdy adres węzła, jak pokazano poniżej:

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


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

Uwaga, ponieważ dopasowałem strukturę węzła, więc gdy malloc () jest węzłem, adres jest wyrównany z 16 bajtami, patrz co najmniej 4 bity. Najmniejsze bity to 0s, tj. 0x0 lub 000b. Więc jeśli masz ten sam specjalny przypadek (wyrównany adres węzła), możesz użyć tych co najmniej 4 bitów. Na przykład, gdy podróżujesz obie listy od początku do końca, ustaw 1 lub 2 z 4 bitów adresu węzła odwiedzającego, to znaczy ustaw flagę;

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

Uwaga, powyższe flagi nie wpłyną na rzeczywisty adres węzła, ale tylko na wartość wskaźnika ZAPISANEGO węzła.

Po znalezieniu ktoś ustawił bit (y) flagi, to pierwszy znaleziony węzeł powinien być punktem scalenia. Po zakończeniu można przywrócić adres węzła, usuwając ustawione bity flagi. podczas gdy ważną rzeczą jest to, że powinieneś być ostrożny podczas iteracji (np. node = node-> next) w celu wyczyszczenia. pamiętaj, że ustawiłeś bity flag, więc zrób w ten sposób

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

Ponieważ ta propozycja przywróci zmienione adresy węzłów, można to uznać za „brak modyfikacji”.

Może być proste rozwiązanie, ale będzie wymagało dodatkowej przestrzeni. Chodzi o to, aby przejść przez listę i zapisać każdy adres na mapie skrótów, teraz przejść przez drugą listę i sprawdzić, czy adres znajduje się na mapie skrótów, czy nie. Każda lista jest przeglądana tylko raz. Żadna lista nie jest modyfikowana. Długość jest nadal nieznana. Wykorzystana przestrzeń pomocnicza: O (n) gdzie „n” jest długością pierwszej listy, przez którą przeszedł.

to rozwiązanie iteruje każdą listę tylko raz ... nie jest też wymagana modyfikacja listy ... chociaż możesz narzekać na spację ..
1) Zasadniczo wykonujesz iterację w liście1 i przechowujesz adres każdego węzła w tablicy (która przechowuje wartość int bez znaku)
2) Następnie iterujesz listę2 i dla adresu każdego węzła ---> przeszukujesz tablicę, w której znajdujesz dopasowanie lub nie ... jeśli to zrobisz, to jest to węzeł scalający

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

Mam nadzieję, że to prawidłowe rozwiązanie ...

Nie ma potrzeby modyfikowania żadnej listy. Istnieje rozwiązanie, w którym każdą listę musimy przejść tylko raz.

1. Utwórz dwa stosy, powiedzmy stck1 i stck2.
2. Przejdź przez pierwszą listę i wypchnij kopię każdego węzła, przez który przechodzisz w stck1.
3. Tak samo jak w kroku drugim, ale tym razem przejrzyj drugą listę i wypchnij kopię węzłów w stck2.
4. Teraz wyjmij z obu stosów i sprawdź, czy dwa węzły są równe, jeśli tak, zachowaj do nich odniesienie. Jeśli nie, to poprzednie węzły, które były równe, są w rzeczywistości punktem scalenia, którego szukaliśmy.

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

Oto naiwne rozwiązanie, nie ma potrzeby przechodzenia przez całe listy.

jeśli twój węzeł strukturalny ma trzy pola, takie jak

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

powiedz, że masz dwie głowy (head1 i head2) wskazujące na nagłówki dwóch list.

Przejrzyj obie listy w tym samym tempie i umieść flagę = 1 (flaga odwiedzonych) dla tego węzła,

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

Co powiesz na to:

1. Jeśli możesz przejść przez każdą listę tylko raz, możesz utworzyć nowy węzeł, przejść przez pierwszą listę, aby każdy węzeł wskazywał na ten nowy węzeł, i przejść przez drugą listę, aby sprawdzić, czy któryś węzeł wskazuje na nowy węzeł ( to jest twój punkt łączenia). Jeśli drugie przejście nie prowadzi do nowego węzła, oryginalne listy nie mają punktu scalenia.

2. Jeśli możesz przeglądać listy więcej niż raz, możesz przejść przez każdą listę, aby znaleźć nasze długości, a jeśli są różne, pomiń „dodatkowe” węzły na początku dłuższej listy. Następnie po prostu przejrzyj obie listy krok po kroku i znajdź pierwszy węzeł scalający.

Kroki w Javie:

1. Utwórz mapę.
2. Rozpocznij przemierzanie w obu gałęziach listy i umieść wszystkie przemierzane węzły listy na Mapę, używając jakiejś unikalnej rzeczy związanej z Węzłami (powiedzmy ID węzła) jako Klucz i umieść Wartości jako 1 na początku dla wszystkich.
3. Kiedy pojawia się pierwszy zduplikowany klucz, zwiększ wartość tego klucza (powiedzmy teraz, że jego wartość wynosi 2, czyli> 1.
4. Pobierz klucz, gdzie wartość jest większa niż 1 i powinien to być węzeł, w którym łączą się dwie listy.

Możemy go skutecznie rozwiązać, wprowadzając pole „isVisited”. Przejdź przez pierwszą listę i ustaw wartość „isVisited” na „true” dla wszystkich węzłów do końca. Teraz zacznij od drugiego i znajdź pierwszy węzeł, w którym flaga jest prawdą i Boom, to twój punkt łączenia.

Krok 1: znajdź długość obu list Krok 2: znajdź różnicę i przesuń największą listę z różnicą Krok 3: Teraz obie listy będą na podobnej pozycji. Krok 4: Powtarzaj listę, aby znaleźć punkt scalenia

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

Użyj mapy lub słownika, aby zapisać adres i wartość węzła. jeśli adres już został odczytany w Mapie / Słowniku, wówczas wartością klucza jest odpowiedź. Ja to zrobiłem:

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

AO (n) rozwiązanie złożoności. Ale na podstawie założenia.

założenie jest takie: oba węzły mają tylko dodatnie liczby całkowite.

logika: zmień wszystkie liczby całkowite z listy1 na ujemne. Następnie przejdź przez list2, aż otrzymasz ujemną liczbę całkowitą. Po znalezieniu => weź to, zmień znak z powrotem na dodatni i wróć.

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

}

Możemy użyć dwóch wskaźników i poruszać się w taki sposób, że jeśli jeden ze wskaźników jest zerowy, wskażemy go na początek drugiej listy i to samo dla drugiej, w ten sposób jeśli długości list są różne, spotkają się w drugim przebiegu . Jeśli długość listy1 jest n, a lista2 jest równa m, ich różnica wynosi d = abs (nm). Pokonają tę odległość i spotkają się w punkcie scalenia.
Kod:

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

Możesz dodać węzły list1do hashset i pętlę przez drugi, a jeśli którykolwiek węzeł list2jest już obecny w zestawie. Jeśli tak, to jest to węzeł scalający

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

Rozwiązanie wykorzystujące 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;
}

Jeśli edytowanie połączonej listy jest dozwolone,

1. Następnie ustaw kolejne wskaźniki węzłów wszystkich węzłów z listy 2 na null.
2. Znajdź wartość danych ostatniego węzła na liście 1. To da ci przecinający się węzeł w pojedynczym przejściu obu list, bez „logiki hi fi”.