[NotABigFan]

Piątunio, więc chill. Zadanko od Googla.

Dane są dwie acykliczne listy jednokierunkowe, które przecinają się w pewnym miejscu. Znajdź to miejsce (pierwszy węzeł wspólny dla obu list). Czas liniowy względem sumy długości list i pamięć stała. Można modyfikować listę.

#programowanie #dailycodingproblem

[pkh]

@NotABigFan: Kazdemu ustawionemu elementowi dodajesz flage visited. I zaczynasz na przemian iterowac po elementach wychodzac z dwoch headow. Jak napotkasz flage visited to znaczy ze drugi head juz to byl, czyli masz punkt wspolny.

[NotABigFan]

@pkh: Pamięć O(n+m)

[NotABigFan]

@NotABigFan: gdzie n i m to długości list, dla jasności

[D.....n]

@NotABigFan: Czy pod "modyfikowanie listy" podpada też przepinanie elementów? Bo jeśli tak, tobym odwrócił listy (O(n + m)), szedł dwoma wskaźnikami do momentu rozjazdu (j.w.) i ponownie odwrócił listy - jeśli jest potrzebne przywrócenie do stanu początkowego.

[NotABigFan]

@Demolicjon: tak ale jakiego rozjazdu? ( ͡° ͜ʖ ͡°) listy jednokierunkowe

[D.....n]

@NotABigFan: Rozjazdu == wykrycia różnych elementów.

[D.....n]

@NotABigFan: A sry, nie doczytałem zadania - wydawało mi się, że listy mają wspólny sufiks, a nie jeden punkt wspólny. Back to the drawing board.

[b.....7]

@NotABigFan: Jako start wybieramy po 1 wskaźniku na dowolny element z każdej z list (i pamiętamy je na boku jako startowe elementy list). Przesuwamy w pętli oba wskaźniki równocześnie o 1 element. Jeśli wrócimy do startowego elementu listy, to przeskakujemy wskaźnikiem na startowy element drugiej listy i iterujemy dalej. Jeśli oba wskaźniki wskazują na ten sam element to koniec.

[D.....n]

@boo007: Nie to zadanie.

[b.....7]

@Demolicjon: nie doczytalem, ale tez powinno dzialac jesli elementy startowe beda poczatkami list i po dojechaniu do konca przeskakujemy na 2 liste

[D.....n]

@boo007: wat

[NotABigFan]

@Demolicjon: Nie no mają wspólny sufiks (nie da się inaczej jeżeli się przecinają). Chodzi o ten pierwszy wspólny element. Rozrysuj sobie jeszcze jak wyglądają te odwrócone listy i zobaczysz, że tam nie ma rozjazdu ( ͡° ͜ʖ ͡°) Zgubisz po prostu jeden prefiks listy.

@boo007: Nie za bardzo kumam. Jak wrócimy do startowego elementu skoro te listy są acykliczne?

[D.....n]

@NotABigFan: Wydaje mi się, że za bardzo kombinuję, ale here goes:

Przypuścmy na chwilę, że te listy trzymają liczby całkowite (potem do tego wrócę). Znajdujemy minimum spośród wszystkich elementów obu list, robimy na nim -1 (żeby otrzymać w ten sposób element unikalny), a następnie wpisujemy go wszędzie do pierwszej listy. Na koniec przechodzimy po drugiej liście szukając pierwszego wystąpienia tego unikalnego elementu.

Jeśli nie mamy do czynienia z liczbami ani innym

[D.....n]

@NotABigFan: OK, czyli sam się zakręciłem w niezrozumieniu i wystarczy psuć dowiązania, żeby znaleźć przecięcie.

[NotABigFan]

@Demolicjon: No usuwamy dowiązania jednej liście i wtedy ostatni element drugiej to nasz szukany.

[b.....7]

@NotABigFan: tak to jest jak się człowiek spieszy i nie doczytać treści. Mój algorytm miał wyglądać jakoś tak w czymś funkcyjnym:

Xs, Ys - wejściowe listy

Znajdzel nil yss = Znajdzel Ys yss
Znajdzel xss nil = Znajdzel xss xs
Znajdzel x:xss y:yss = if(x==y) return x
Else Znajdzel xss yss

Uruchamiamy
Znajdzel Xs ys

Ten kod powinien zwrócić wspólny element, można jeszcze gdzieś trzymać indeksy, jeśli chcemy znalesc miejsce, ale

[NotABigFan]

@boo007: spoko luz, jak wrócisz i znajdziesz czas to napisz to w czymś wykonywalnym, bo dalej nie kumam ( ͡° ͜ʖ ͡°)

[S.....s]

@NotABigFan co znaczy przecinają się?

[NotABigFan]

@SuppressWarnings: że istnieje co najmniej jeden element wspólny

[S.....s]

@NotABigFan czyli jeśli lista ma nody (value,next) to element wspólny to ten z taką samą wartością? Bo jeśli node byłby wspólny to listy by się łączyły