Scal dwie posortowane listy
Szczegółowy przewodnik i implementacja Python dla problemu „Scal dwie posortowane listy”.
1. Ucz się
Problem „Scal dwie posortowane listy” jest kluczowym wyzwaniem w sekcji Lista połączona.
Ta implementacja koncentruje się na logice prostego poziomu w Python.
W dostarczanych przez nas rozwiązaniach priorytetem jest dokładność techniczna i czytelność kodu.
2. Real-World Applications
3. Visual Intuition
Wizualizacja przepływu logicznego dla Scal dwie posortowane listy.
4. Prerequisites
5. Step-by-Step Thinking
1. Understand the problem
Przeczytaj uważnie opis problemu dla Scal dwie posortowane listy.
2. Formulate brute force
Zaprojektuj proste rozwiązanie iteracyjne.
3. Identify inefficiency
Poszukaj zbędnych obliczeń.
4. Optimize search path
Użyj funkcji mieszania lub sortowania, aby przyspieszyć proces.
5. Final Implementation
Oczyść kod dla standardów produkcyjnych.
Oświadczenie o problemie
Otrzymasz głowy dwóch posortowanych połączonych list list1 i list2. Połącz obie listy w jedną posortowaną listę. Listę należy utworzyć łącząc ze sobą węzły dwóch pierwszych list. Zwróć nagłówek połączonej listy połączonej.
Połączone listy są reprezentowane jako listy Python. Zaimplementuj funkcję mergeTwoLists(list1: list, list2: list) -> list, która zwraca połączoną posortowaną listę.
- •The number of nodes in both lists is in the range [0, 50]
- •-100 <= Node.val <= 100
- •Both list1 and list2 are sorted in non-decreasing order
Przykłady
[1,2,4], [1,3,4]
[1,1,2,3,4,4]
Merging 1->2->4 and 1->3->4 gives 1->1->2->3->4->4.
[], []
[]
Both lists are empty, so the merged list is also empty.
[], [0]
[0]
Merging an empty list with [0] gives [0].
Need a Hint?
Edge Cases to Watch
- Puste struktury wejściowe
- Wejścia jednoelementowe
- Duże granice liczbowe
Gotowy do rozwiązania?
Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.
Spostrzeżenia i odmiany wywiadu
Podział analizy złożoności
Dlaczego Czas: Directly evaluates all possibilities.
Dlaczego kosmos: Uses standard local memory.
Dlaczego Czas: Optimized paths reduce total operations.
Dlaczego kosmos: May trade memory for speed.
Zoptymalizowany kod rozwiązania w języku Python
Zoptymalizowany kod rozwiązania w języku Python
def merge_two_lists_opt(list1, list2):
if isinstance(list1, list):
l1 = build_linked_list(list1)
l2 = build_linked_list(list2)
res = merge_two_lists_opt_helper(l1, l2)
return linked_list_to_list(res)
return merge_two_lists_opt_helper(list1, list2)
def merge_two_lists_opt_helper(list1: ListNode, list2: ListNode) -> ListNode:
dummy = ListNode(0)
tail = dummy
while list1 and list2:
if list1.val < list2.val:
tail.next = list1
list1 = list1.next
else:
tail.next = list2
list2 = list2.next
tail = tail.next
tail.next = list1 or list2
return dummy.nextKod brutalnej siły (chroniony spoilerami)
Kod brutalnej siły (chroniony spoilerami)
def merge_two_lists_brute(list1, list2):
if isinstance(list1, list):
l1 = build_linked_list(list1)
l2 = build_linked_list(list2)
res = merge_two_lists_brute_helper(l1, l2)
return linked_list_to_list(res)
return merge_two_lists_brute_helper(list1, list2)
def merge_two_lists_brute_helper(list1: ListNode, list2: ListNode) -> ListNode:
vals = []
curr = list1
while curr:
vals.append(curr.val)
curr = curr.next
curr = list2
while curr:
vals.append(curr.val)
curr = curr.next
vals.sort()
dummy = ListNode(0)
curr = dummy
for v in vals:
curr.next = ListNode(v)
curr = curr.next
return dummy.nextAlgorithm Pattern Checklist
When dealing with Linked List data patterns.
- Are constraints clear?
- Is there a linear or logarithmic optimization possible?
Key Revision Notes
Obowiązują standardowe właściwości problemu z listą połączoną.
Powiązane pytania
PyRun is built and maintained by an independent solo developer. If this helped your interview prep, consider buying a coffee!
Polecane zasoby Pythona
Poszerzaj swoją wiedzę dzięki powiązanym interaktywnym samouczkom, ściągawkom i porównaniom kodów.
Listy Pythona
Dowiedz się wszystkiego o listach w Pythonie. Odkryj, jak tworzyć, wycinać, modyfikować i iterować po tablicach natywnie w języku Python.
Jak połączyć dwie listy w Pythonie
Poznaj najlepsze sposoby scalania i łączenia dwóch list w Pythonie. Porównaj operator plus, metodę rozszerzenia, rozpakowywanie listy i opcje łańcucha.
Ściągawka dotycząca metod ciągów w Pythonie
Kompletny przewodnik dotyczący manipulacji ciągami znaków w języku Python. Opanuj formatowanie, wyszukiwanie, dzielenie, zastępowanie i sprawdzanie właściwości ciągów.
Python kontra JavaScript: który język programowania jest najlepszy?
Kompleksowe porównanie Pythona i JavaScript. Poznaj różnice w składni, wydajność, przypadki użycia (backend vs frontend) i przykłady kodowania.