To jest pytanie programistyczne zadawane podczas testu pisemnego na rozmowę kwalifikacyjną. „Masz dwie pojedynczo połączone listy, które są już posortowane, musisz je scalić i zwrócić nagłówek nowej listy bez tworzenia żadnych nowych dodatkowych węzłów. Zwrócona lista również powinna zostać posortowana”
Podpis metody to: Node MergeLists (lista węzłów1, lista węzłów2);
Klasa węzła jest poniżej:
class Node{
int data;
Node next;
}
Próbowałem wielu rozwiązań, ale nie tworzyłem dodatkowego węzła. Proszę pomóż.
Oto towarzyszący wpis na blogu http://techieme.in/merging-two-sorted-singly-linked-list/
algorithm
singly-linked-list
dharam
źródło
źródło
Odpowiedzi:
źródło
Rekursja nie powinna być potrzebna, aby uniknąć przydzielenia nowego węzła:
źródło
if (list1.next == null) list1.next = list2;
po prostu może byćlist1.next = list2;
. Ponieważwhile (list1.next != null)
pętla właśnie się zakończyła, możemy być tego pewnilist1.next == null
.źródło
Oto algorytm łączenia dwóch posortowanych połączonych list A i B:
Tutaj C będzie listą wyników.
źródło
Spójrz mamo, bez rekurencji!
źródło
Iterację można wykonać jak poniżej. Złożoność = O (n)
źródło
źródło
Można to zrobić bez tworzenia dodatkowego węzła, z tylko kolejnym odwołaniem do węzła przekazującym parametry (temp. Węzła).
źródło
Chciałbym podzielić się tym, jak pomyślałem o rozwiązaniu ... widziałem rozwiązanie, które obejmuje rekursję i są one całkiem niesamowite, jest wynikiem dobrze funkcjonalnego i modułowego myślenia. Naprawdę doceniam dzielenie się.
Chciałbym dodać, że rekurencja nie będzie działać dla dużych litów, wywołania stosu będą przepełnione; więc zdecydowałem się wypróbować podejście iteracyjne ... i oto, co otrzymałem.
Kod jest dość oczywisty, dodałem kilka komentarzy w wierszu, aby to zapewnić.
Jeśli go nie dostaniesz, powiadom mnie, a poprawię czytelność (być może mam mylącą interpretację własnego kodu).
}
źródło
Proste rozwiązanie iteracyjne.
źródło
Poniżej przedstawiam rozwiązanie iteracyjne. Rozwiązanie rekurencyjne byłoby bardziej zwarte, ale ponieważ nie znamy długości list, rekursja grozi przepełnieniem stosu.
Podstawowa idea jest podobna do kroku scalania w sortowaniu przez scalanie; trzymamy wskaźnik odpowiadający każdej liście wejściowej; przy każdej iteracji przesuwamy do przodu wskaźnik odpowiadający mniejszemu elementowi. Jest jednak jedna zasadnicza różnica, w której większość ludzi się przewraca. W sortowaniu przez scalanie, ponieważ używamy tablicy wyników, następną pozycją do wstawienia jest zawsze indeks tablicy wyników. W przypadku listy połączonej musimy zachować wskaźnik do ostatniego elementu posortowanej listy. Wskaźnik może przeskakiwać z jednej listy wejściowej do drugiej, w zależności od tego, która z nich ma mniejszy element dla bieżącej iteracji.
W związku z tym poniższy kod powinien być zrozumiały.
źródło
Prosty kod w javascript do scalenia dwóch połączonych list w miejscu.
źródło
Przede wszystkim należy zrozumieć, co oznacza „bez tworzenia żadnych nowych dodatkowych węzłów”. Jak rozumiem, nie oznacza to, że nie mogę mieć wskaźnika (ów) wskazującego na istniejący (e) węzeł (y).
Nie możesz tego osiągnąć bez mówienia wskaźników do istniejących węzłów, nawet jeśli użyjesz rekurencji, aby osiągnąć to samo, system utworzy wskaźniki dla Ciebie jako stosy wywołań. To tak, jak nakazanie systemowi dodania wskaźników, których uniknąłeś w swoim kodzie.
Prosta funkcja, aby osiągnąć to samo dzięki dodatkowym wskazówkom :
źródło
Proszę odnieść się do mojego posta na blogu http://www.algorithmsandme.com/2013/10/linked-list-merge-two-sorted-linked.html
źródło
źródło
Oto kompletny przykład roboczy korzystający z połączonej listy zaimplementowanej java.util. Możesz po prostu skopiować i wkleić poniższy kod do metody main ().
źródło
Sposób rekurencyjny (wariant odpowiedzi Stefana)
Rozważ poniższą listę połączoną, aby to zwizualizować
2>4
lista A1>3
lista BPrawie taka sama odpowiedź (nierekurencyjna) jak Stefan, ale z trochę większą liczbą komentarzy / znaczącą nazwą zmiennej. Uwzględniono również listę podwójnych linków w komentarzach, jeśli ktoś jest zainteresowany
Rozważmy przykład
5->10->15>21 // List1
2->3->6->20 //List2
źródło
Moje podejście do pytania jest następujące:
Pseudo kod:
Kod:
źródło
źródło
źródło
:) GlbMP
źródło
public static Node merge(Node h1, Node h2) { Node h3 = new Node(0); Node current = h3; boolean isH1Left = false; boolean isH2Left = false; while (h1 != null || h2 != null) { if (h1.data <= h2.data) { current.next = h1; h1 = h1.next; } else { current.next = h2; h2 = h2.next; } current = current.next; if (h2 == null && h1 != null) { isH1Left = true; break; } if (h1 == null && h2 != null) { isH2Left = true; break; } } if (isH1Left) { while (h1 != null) { current.next = h1; current = current.next; h1 = h1.next; } } if (isH2Left) { while (h2 != null) { current.next = h2; current = current.next; h2 = h2.next; } } h3 = h3.next; return h3; }
źródło
Na początku utworzyłem tylko jeden fikcyjny węzeł, aby zaoszczędzić sobie wielu warunków „jeśli”.
źródło
źródło
źródło
Oto kod, jak połączyć dwie posortowane połączone listy headA i headB:
źródło