0Pricing
Coding Interview Prep · Lekcja

Scalanie, dzielenie i znajdowanie n-tego elementu od końca

Scalą Państwo dwie posortowane listy jednokierunkowe w O(n), podzielą listę w punkcie środkowym za pomocą wolnych i szybkich wskaźników oraz znajdą n-ty węzeł od końca.

Scalanie, dzielenie i znajdowanie n-tego elementu od końca to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Trzy podstawowe wzorce dla list wiązanych

Ta lekcja obejmuje trzy podstawowe operacje na listach wiązanych, które stale pojawiają się jako elementy składowe trudniejszych zadań: scalanie dwóch posortowanych list (wykorzystywane w sortowaniu przez scalanie i scalaniu K-kierunkowym), dzielenie listy w punkcie środkowym (wykorzystywane w sortowaniu przez scalanie i wykrywaniu palindromów) oraz znajdowanie n-tego węzła od końca (wykorzystywane w remove-nth-from-end).

Wszystkie trzy operacje opierają się na technikach poznanych wcześniej: fikcyjnym węźle początkowym, wolnym i szybkim wskaźniku oraz uważnym kontrolowaniu granic.

Scalanie dwóch posortowanych list

LeetCode 21 „Merge Two Sorted Lists”: mając dwie posortowane listy wiązane, należy zwrócić jedną scaloną, posortowaną listę. Należy użyć fikcyjnego węzła początkowego i wskaźnika ogona curr. Przy każdym kroku trzeba porównać głowy obu list i dołączyć mniejszy węzeł do curr. Gdy jedna lista się wyczerpie, należy dołączyć resztę drugiej. Czas: O(n+m), pamięć: O(1) (przepinanie wskaźników w miejscu).

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1, l2):
    dummy = ListNode(0)
    curr  = dummy
    while l1 and l2:
        if l1.val <= l2.val:
            curr.next = l1
            l1 = l1.next
        else:
            curr.next = l2
            l2 = l2.next
        curr = curr.next
    curr.next = l1 or l2  # attach remaining nodes
    return dummy.next

def build(arr):
    d = ListNode(); c = d
    for v in arr:
        c.next = ListNode(v); c = c.next
    return d.next

def to_list(h):
    r=[]
    while h: r.append(h.val); h=h.next
    return r

print(to_list(mergeTwoLists(build([1,2,4]), build([1,3,4]))))

Śledzenie scalania krok po kroku

Prześledź mergeTwoLists([1,2,4], [1,3,4]): porównaj 1 i 1 — wybierz l1(1), przesuń l1 na 2. Porównaj 2 i 1 — wybierz l2(1), przesuń l2 na 3. Porównaj 2 i 3 — wybierz l1(2), przesuń l1 na 4. Porównaj 4 i 3 — wybierz l2(3), przesuń l2 na 4. Porównaj 4 i 4 — wybierz l1(4), przesuń l1 na None. Dołącz pozostałe l2(4). Wynik: [1,1,2,3,4,4].

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeTwoLists(l1, l2):
    dummy = ListNode(0)
    curr  = dummy
    step  = 0
    while l1 and l2:
        step += 1
        if l1.val <= l2.val:
            print(f'Step {step}: pick l1({l1.val})')
            curr.next = l1; l1 = l1.next
        else:
            print(f'Step {step}: pick l2({l2.val})')
            curr.next = l2; l2 = l2.next
        curr = curr.next
    curr.next = l1 or l2
    return dummy.next

def build(arr):
    d=ListNode();c=d
    for v in arr: c.next=ListNode(v);c=c.next
    return d.next

mergeTwoLists(build([1,2,4]),build([1,3,4]))

Znajdowanie punktu środkowego za pomocą wolnego i szybkiego wskaźnika

Aby podzielić listę w punkcie środkowym, należy użyć wzorca wolnego i szybkiego wskaźnika. slow przesuwa się o 1 krok, a fast o 2 kroki. Gdy fast dociera do None (lub do ostatniego węzła), slow znajduje się w punkcie środkowym. W przypadku listy o parzystej długości daje to pierwszy z dwóch środkowych węzłów, co jest standardowym rozwiązaniem przy dzieleniu na potrzeby sortowania przez scalanie.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def split_at_mid(head):
    '''Returns (first_half_head, second_half_head).'''
    slow, fast = head, head
    while fast.next and fast.next.next:
        slow = slow.next
        fast = fast.next.next
    mid = slow.next   # second half starts here
    slow.next = None  # sever the list
    return head, mid

def build(arr):
    d=ListNode();c=d
    for v in arr: c.next=ListNode(v);c=c.next
    return d.next

def to_list(h):
    r=[]
    while h: r.append(h.val); h=h.next
    return r

head=build([1,2,3,4,5])
first, second = split_at_mid(head)
print(to_list(first), to_list(second))  # [1,2,3] [4,5]

Sortowanie przez scalanie listy wiązanej

LeetCode 148 „Sort List”: posortowanie listy wiązanej w czasie O(n log n) i przy użyciu O(log n) pamięci. Podejście polega na podzieleniu listy w punkcie środkowym, rekurencyjnym posortowaniu obu połówek i ich scaleniu. Sortowanie przez scalanie listy wiązanej jest naturalnym wyborem, ponieważ podział w punkcie środkowym zajmuje O(n) (a nie O(1), jak w przypadku tablic), jednak całkowita złożoność nadal wynosi O(n log n), a stos wywołań zajmuje tylko O(log n) pamięci.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def sortList(head):
    if not head or not head.next:
        return head
    # Split
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    mid = slow.next
    slow.next = None
    # Recurse
    left  = sortList(head)
    right = sortList(mid)
    # Merge
    dummy = ListNode(0)
    curr  = dummy
    while left and right:
        if left.val <= right.val:
            curr.next = left;  left  = left.next
        else:
            curr.next = right; right = right.next
        curr = curr.next
    curr.next = left or right
    return dummy.next

def build(arr):
    d=ListNode();c=d
    for v in arr: c.next=ListNode(v);c=c.next
    return d.next
def to_list(h):
    r=[]
    while h: r.append(h.val);h=h.next
    return r

print(to_list(sortList(build([4,2,1,3]))))  # [1,2,3,4]

Znajdowanie n-tego węzła od końca

LeetCode 19 „Remove Nth Node From End of List”: znalezienie n-tego węzła od ogona w jednym przejściu. Należy użyć dwóch wskaźników oddalonych od siebie dokładnie o n węzłów. Najpierw przesunąć fast o n kroków przed slow. Następnie przesuwać oba wskaźniki jednocześnie, aż fast dotrze do ostatniego węzła. Wtedy slow wskazuje (n+1)-szy węzeł od końca — poprzednik węzła, który należy usunąć.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def removeNthFromEnd(head, n):
    dummy = ListNode(0, head)
    fast = dummy
    for _ in range(n + 1):  # advance fast n+1 steps
        fast = fast.next
    slow = dummy
    while fast:             # advance both until fast is None
        slow = slow.next
        fast = fast.next
    slow.next = slow.next.next  # remove nth node
    return dummy.next

def build(arr):
    d=ListNode();c=d
    for v in arr: c.next=ListNode(v);c=c.next
    return d.next
def to_list(h):
    r=[]
    while h: r.append(h.val);h=h.next
    return r

print(to_list(removeNthFromEnd(build([1,2,3,4,5]), 2)))  # [1,2,3,5]

Dlaczego w Remove Nth potrzeba n+1 kroków

Kluczowy szczegół polega na przesunięciu fast o n+1 kroków (a nie n) od głowy pomocniczej. Po n+1 krokach fast znajduje się o n+1 pozycji przed slow (oba wskaźniki zaczynają od głowy pomocniczej). Gdy fast osiąga wartość None (jedną pozycję za ogonem), slow znajduje się o n+1 pozycji przed None — oznacza to, że wskazuje pozycję (length - n - 1), licząc od zera, czyli poprzednik docelowego węzła. Dzięki temu instrukcja slow.next = slow.next.next może w prosty sposób usunąć n-ty węzeł od końca.

# Visual: list = [1,2,3,4,5], n=2
# dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> None
# After n+1=3 forward steps from dummy, fast=3
# dummy(slow)  1  2  3(fast)  4  5  None
# Advance both until fast=None:
# Step 1: slow=1, fast=4
# Step 2: slow=2, fast=5
# Step 3: slow=3, fast=None
# slow is at 3, slow.next=4 (the 2nd from end) -> delete
print('slow.next (to delete): 4')
print('Result: [1, 2, 3, 5]')

Punkt przecięcia dwóch list wiązanych

LeetCode 160 „Intersection of Two Linked Lists”: znalezienie węzła, w którym dwie listy po raz pierwszy się przecinają. Sposób wykorzystujący O(1) pamięci polega na przesuwaniu dwóch wskaźników, po jednym dla każdej listy. Gdy wskaźnik osiągnie None, należy przekierować go na głowę drugiej listy. Po co najwyżej len(A) + len(B) krokach oba wskaźniki pokonają tę samą łączną odległość i muszą znaleźć się w punkcie przecięcia (albo oba wskazywać None, jeśli listy się nie przecinają).

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def getIntersectionNode(headA, headB):
    a, b = headA, headB
    while a is not b:
        a = a.next if a else headB
        b = b.next if b else headA
    return a  # None if no intersection

# Build: A: 4->1->\  B: 5->6->1->\ both -> 8->4->5
shared = [ListNode(v) for v in [8, 4, 5]]
shared[0].next = shared[1]; shared[1].next = shared[2]
A = ListNode(4); A.next = ListNode(1); A.next.next = shared[0]
B = ListNode(5); B.next = ListNode(6); B.next.next = ListNode(1); B.next.next.next = shared[0]
print(getIntersectionNode(A, B).val)  # 8

Scalanie k posortowanych list (dziel i zwyciężaj)

LeetCode 23 „Merge K Sorted Lists”: mając k posortowanych list, należy scalić je w jedną. Optymalne podejście polega na wielokrotnym scalaniu par list metodą dziel i zwyciężaj, zmniejszając o połowę liczbę list w każdej rundzie. Dla k list o średniej długości n zajmuje to O(n k log k), w przeciwieństwie do O(n k²) przy scalaniu sekwencyjnym. Podejście z kopcem minimalnym również ma złożoność O(n k log k).

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeKLists(lists):
    def merge_two(l1, l2):
        dummy = ListNode(0); curr = dummy
        while l1 and l2:
            if l1.val <= l2.val:
                curr.next = l1; l1 = l1.next
            else:
                curr.next = l2; l2 = l2.next
            curr = curr.next
        curr.next = l1 or l2
        return dummy.next

    if not lists: return None
    while len(lists) > 1:
        merged = []
        for i in range(0, len(lists), 2):
            l1 = lists[i]
            l2 = lists[i+1] if i+1 < len(lists) else None
            merged.append(merge_two(l1, l2))
        lists = merged
    return lists[0]

def build(arr):
    d=ListNode();c=d
    for v in arr: c.next=ListNode(v);c=c.next
    return d.next
def to_list(h):
    r=[]
    while h: r.append(h.val);h=h.next
    return r

lists=[build([1,4,5]),build([1,3,4]),build([2,6])]
print(to_list(mergeKLists(lists)))  # [1,1,2,3,4,4,5,6]

Lista wiązana z węzłami o indeksach nieparzystych i parzystych

LeetCode 328 „Odd Even Linked List”: należy najpierw umieścić wszystkie węzły o nieparzystych indeksach, a następnie węzły o parzystych indeksach (indeksowanie od 1). Podejście polega na utrzymywaniu dwóch osobnych łańcuchów (nieparzystego i parzystego) oraz połączeniu ich na końcu. Wystarczy jedno przejście przez listę, co daje O(n) czasu i O(1) pamięci. To przejrzysty przykład jednoczesnego przesuwania dwóch wskaźników z różnymi krokami.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def oddEvenList(head):
    if not head:
        return head
    odd  = head
    even = head.next
    even_head = even
    while even and even.next:
        odd.next  = even.next
        odd       = odd.next
        even.next = odd.next
        even      = even.next
    odd.next = even_head
    return head

def build(arr):
    d=ListNode();c=d
    for v in arr: c.next=ListNode(v);c=c.next
    return d.next
def to_list(h):
    r=[]
    while h: r.append(h.val);h=h.next
    return r

print(to_list(oddEvenList(build([1,2,3,4,5]))))  # [1,3,5,2,4]

Składanie wszystkiego w całość

Trzy wzorce z tej lekcji — scalanie posortowanych list, podział w punkcie środkowym i znajdowanie n-tego elementu od końca — mają wspólną cechę: wykorzystują dodatkowe zmienne przechowujące wskaźniki do śledzenia pozycji bez używania dodatkowej pamięci. Głowa pomocnicza upraszcza scalanie i usuwanie; odstęp między wolnym a szybkim wskaźnikiem wskazuje konkretną pozycję względną; wcześniejsze przesunięcie jednego wskaźnika tworzy wymagany odstęp.

Podczas rozmowy kwalifikacyjnej warto przed rozpoczęciem kodowania nazwać używany wzorzec: „Użyję techniki dwóch wskaźników z odstępem, aby znaleźć n-ty element od końca w jednym przejściu”. Pokazuje to uporządkowany sposób myślenia.

Szybki test

Sprawdź swoją wiedzę z zagadnień Data Structures & Algorithms — Coding Interview Prep omówionych w tej lekcji.

Podsumowanie lekcji

W tej lekcji nauczyłeś się, że: scalanie dwóch posortowanych list wykorzystuje głowę pomocniczą i porównywanie na każdym kroku, zapewniając O(n+m) czasu i O(1) pamięci, podział w punkcie środkowym wykorzystuje wolny i szybki wskaźnik, przy czym szybki zatrzymuje się na ostatniej poprawnej parze, a znalezienie n-tego elementu od końca wymaga przesunięcia szybkiego wskaźnika o n+1 kroków, aby wolny wskaźnik znalazł się na poprzedniku. W następnej części zbudujemy stosy i kolejki oraz zastosujemy je do klasycznych zadań rekrutacyjnych.

Często zadawane pytania

Czy lekcja „Scalanie, dzielenie i znajdowanie n-tego elementu od końca” jest bezpłatna?

Tak — pełny tekst „Scalanie, dzielenie i znajdowanie n-tego elementu od końca” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.

Co nauczysz się w „Scalanie, dzielenie i znajdowanie n-tego elementu od końca”?

Scalą Państwo dwie posortowane listy jednokierunkowe w O(n), podzielą listę w punkcie środkowym za pomocą wolnych i szybkich wskaźników oraz znajdą n-ty węzeł od końca. Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?

Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.

Ile czasu zajmuje lekcja „Scalanie, dzielenie i znajdowanie n-tego elementu od końca”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?

Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

  1. Klasa Node i tworzenie listy
  2. Odwracanie listy jednokierunkowej
  3. Wykrywanie cyklu algorytmem Floyda
  4. Scalanie, dzielenie i znajdowanie n-tego elementu od końca
← Powrót do Coding Interview Prep