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

Poniżej jest zdecydowanie największym ze wszystkich, jakie widziałem-O (N), bez liczników. Mam go podczas rozmowy kwalifikacyjnej z kandydatem S. N. w VisionMap .

zrób interwałowy wskaźnik w ten sposób: idzie do przodu za każdym razem do końca, a następnie przeskakuje na początek przeciwnej listy i tak dalej. Stwórz dwie z nich, wskazując na dwie głowy. Zalicz każdy wskaźnik o 1 za każdym razem, aż się spotkają. stanie się to po jednym lub dwóch przejazdach.

I still użyj tego pytania w wywiadach-ale aby zobaczyć, jak długo zajmuje komuś zrozumienie, dlaczego to rozwiązanie działa.

ODPOWIEDŹ Pawła wymaga modyfikacji List oraz iterowania każdej listy dwukrotnie.

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

Chodzi o ignorowanie początkowych wpisów dłuższej listy (punkt scalania nie może tam być), tak aby Dwa wskaźniki były w równej odległości od końca listy. Następnie przesuń je do przodu, aż / align = "left" /

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 ten sam (czas liniowy) co moja druga odpowiedź, ale prawdopodobnie ma mniejsze stałe, więc jest prawdopodobnie szybszy. Ale myślę, że moja druga odpowiedź jest fajniejsza.

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

Powiedz, że zaczynasz od:

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

1) przejść 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 scalenia.

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

Jeśli moglibyśmy iterować listy dokładnie dwa razy, to mogę podać metodę wyznaczania punktu scalenia:

• iteracja obu list i obliczanie długości A i B
• Oblicz różnicę długości C = /A-B/;
• Zacznij iterować obie listy jednocześnie, ale wykonaj dodatkowe kroki C na liście, które były większe
• te dwa wskaźniki spotkają się ze sobą w punkcie scalania

To prawdopodobnie narusza warunek "parse each list only once" , ale zaimplementuj algorytm tortoise and hare (używany do znalezienia punktu scalania i długości cyklu listy cyklicznej), więc zaczynasz od listy A, a kiedy osiągniesz NULL na końcu 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ę scalenie (zmienna " mu " według Wikipedii opis).

Ponadto, wartość "lambda" informuje o długości listy B, a jeśli chcesz, możesz obliczyć długość listy A podczas algorytmu(gdy przekierowujesz link NULL).

Oto rozwiązanie, szybkie obliczeniowo (iteruje każdą listę raz), 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. Iteruj przez jedną listę i dodaj każdy węzeł do zestawu. Następnie przejrzyj drugą listę i dla każdej iteracji sprawdź, czy węzeł istnieje w zestawie. Jeśli tak, to znalazłeś swój punkt scalenia:)

Może jestem za upraszczaniem tego, ale po prostu iteruję najmniejszą listę i używam ostatnich węzłów Link jako punktu scalania?

Gdzie Data->Link->Link == NULL jest punktem końcowym, dając Data->Link jako punkt scalający (na końcu listy).

EDIT:

Okej, z zamieszczonego zdjęcia analizujesz dwie listy, najmniejszą najpierw. Z najmniejszą listą możesz zachować odniesienia do następującego węzła. Teraz, kiedy analizujesz drugą listę, robisz porównanie w odniesieniu do Znajdź, gdzie Reference [i] jest referencją w LinkedList [i]->Link. To da punkt połączenia. Czas wyjaśnić obrazkami(nakładać wartości na obrazek OP).

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

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

Masz drugą podlinkowaną listę:

1->2->

Z połączoną listą odniesienia następują następująco:

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

Dlatego mapujemy pierwszą "mniejszą" listę (jako scaloną listę, czyli liczenie ma długość 4 i główną listę 5)

Przejrzyj pierwszą listę, zachowaj odniesienie do referencji.

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

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

Oczywiście, utrzymujesz nową listę wskaźników, ale to nie jest poza specyfikacją. Jednak pierwsza lista jest przetwarzana dokładnie raz, a druga lista będzie w pełni przetwarzana tylko wtedy, gdy nie ma punktu scalania. Inaczej skończy się szybciej (na punkt scalenia).

Przetestowałem przypadek scalenia 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ż wyrównałem strukturę węzła, więc gdy malloc () jest węzłem, adres jest wyrównany w / 16 bajtów, zobacz co najmniej 4 bity. Najmniejsze bity to 0s, czyli 0x0 lub 000B. Więc jeśli jesteś w tym samym specjalnym przypadku (wyrównany adres węzła) też, możesz użyć tych co najmniej 4 bitów. Na przykład, gdy podróżujesz obie listy od głowy do ogona, Ustaw 1 lub 2 z 4 bitów adresu węzła odwiedzającego, oznacza to, że ustawiamy flagę;

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

Uwaga powyżej znaczników nie wpłynie na rzeczywisty adres węzła, ale tylko na zapisaną wartość wskaźnika węzła.

Gdy znaleziony ktoś ustawił bit(y) flagi, to pierwszym znalezionym węzłem powinien być punkt scalenia. po zakończeniu przywracasz adres węzła poprzez wyczyszczenie ustawionych bitów flagi. chociaż ważną rzeczą jest to, że powinieneś być ostrożny, gdy iterate (np. node = node- > next) zrobić czyste. pamiętaj, że ustawiłeś bit flagi, więc zrób to 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 zmodyfikowane adresy węzłów, można ją uznać za "Bez Modyfikacji".

To rozwiązanie powtarza tylko każdą listę once...no wymagana jest również modyfikacja listy..chociaż możesz narzekać na przestrzeń..
1) W zasadzie iterat w list1 i przechowywać adres każdego węzła w tablicy(która przechowuje unsigned int wartość)
2) następnie iterujesz list2, a dla każdego adresu węzła - - - > przeszukujesz tablicę, która pasuje 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 jest to poprawne rozwiązanie...

Oto naiwne rozwiązanie , nie trzeba przechodzić przez całe listy.

Jeśli Twój węzeł strukturalny ma trzy pola typu

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

Powiedzmy, że masz dwie głowy (head1 i head2) wskazujące na głowę dwóch list.

Przemierzaj obie listy w tym samym tempie i umieść flagę =1 (odwiedzona Flaga) dla tego węzła,

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

A może tak:

1. Jeśli możesz przejść każdą listę tylko raz, możesz utworzyć nowy węzeł, przejść pierwszą listę, aby każdy punkt węzła do tego nowego węzła, a następnie przejść drugą listę, aby sprawdzić, czy jakikolwiek węzeł wskazuje na nowy węzeł (to twój punkt scalenia). Jeśli drugie przejście nie prowadzi do nowego węzła, to oryginalne listy nie mają punktu scalania.

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

Kroki w Javie:

1. Utwórz mapę.
2. Zacznij przemierzać obie gałęzie listy i umieść wszystkie przejechane węzły listy na mapie używając jakiejś unikalnej rzeczy związanej z węzłami (powiedzmy Node Id) jako klucza i umieść wartości jako 1 na początku dla wszystkich.
3. Kiedy pojawia się pierwszy zduplikowany klucz, zwiększ wartość tego klucza (powiedzmy, że teraz jego wartość stała się 2, która wynosi > 1.
4. Get The Key where the value is larger than 1 and that should be the node where two lists are / align = "left" /

Możemy go skutecznie rozwiązać wprowadzając pole "isVisited". Przejdź 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 prawdziwa i Boom, to twój punkt scalania.

Krok 1: Znajdź długość zarówno listy Krok 2: Znajdź różnicę i przesuń największą listę z różnicą Krok 3: teraz obie listy będą w podobnej pozycji. Krok 4: Iteruj przez 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żeli adres już istnieje w mapie/słowniku, to wartością klucza jest odpowiedź. Zrobiłem to:

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

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

1. Utwórz dwa stosy, powiedzmy stck1 i stck2.
2. Trawersuj pierwszą listę i wypychaj kopię każdego węzła, który przemierzasz w stck1.
3. to samo co krok drugi, ale tym razem przejdź drugą listę i wypchnij kopię węzłów w stck2.
4. Teraz, pop z obu stosów i sprawdzić, czy dwa węzły są równe, jeśli tak, to zachować odniesienie do nich. Jeśli nie, to poprzednie węzły / align = "center" bgcolor = "# e0ffe0 " / cesarz chin / / align = center /

Może być proste rozwiązanie, ale będzie wymagało przestrzeni pomocniczej. Chodzi o to, aby przejść listę i zapisać każdy adres na mapie hash, teraz przejść drugą listę i dopasować, czy adres znajduje się na mapie hash, czy nie. Każda lista jest przejeżdżana tylko raz. Nie ma żadnych modyfikacji na żadnej liście. Długość jest nadal nieznana. Używana przestrzeń pomocnicza: O (n), gdzie " n " jest długością pierwszej listy.

Rozwiązanie O(n) złożoności. Ale opierając się na założeniu.

Założenie jest następujące: oba węzły mają tylko dodatnie liczby całkowite.

Logika: niech cała liczba całkowita list1 będzie ujemna. Następnie przejdź przez listę2, aż otrzymasz ujemną liczbę całkowitą. Po znalezieniu = > weź go, Zmień znak z powrotem na pozytywny i powrót.

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

}