Yhdistäminen, jakaminen ja n:nnen alkion etsiminen lopusta
Yhdistäkää kaksi järjestettyä linkitettyä listaa ajassa O(n), jakakaa lista keskikohdasta hitaiden ja nopeiden osoittimien avulla ja etsikää n:s solmu hännästä lukien.
Yhdistäminen, jakaminen ja n:nnen alkion etsiminen lopusta on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 4/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Kolme keskeistä linkitetyn listan mallia
Tässä oppitunnissa käsitellään kolme linkitettyjen listojen perustavanlaatuista toimintoa, jotka toimivat jatkuvasti vaikeampien ongelmien rakennuspalikoina: kahden järjestetyn listan yhdistäminen (käytetään lomituslajittelussa ja K-way merge -yhdistämisessä), listan jakaminen keskikohdasta (käytetään lomituslajittelussa ja palindromin tunnistuksessa) sekä n:nnen solmun etsiminen lopusta (käytetään remove-nth-from-end-toiminnossa).
Kaikki kolme perustuvat jo näkemiinne tekniikoihin: dummy head -solmuun, hitaisiin ja nopeisiin osoittimiin sekä rajojen huolelliseen seurantaan.
Kahden järjestetyn listan yhdistäminen
LeetCode 21:n 'Merge Two Sorted Lists' -tehtävässä annetaan kaksi järjestettyä linkitettyä listaa, ja tehtävänä on palauttaa yksi yhdistetty järjestetty lista. Käyttäkää dummy head -solmua ja curr-häntäosoitinta. Verratkaa kullakin askeleella listojen alkusolmuja ja liittäkää pienempi solmu osoittimeen curr. Kun toinen lista loppuu, liittäkää toisen listan loppuosa. Aikavaativuus: O(n+m), tilavaativuus: O(1) (osoittimien uudelleenreititys paikallaan).
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]))))Yhdistämisen vaiheittainen läpikäynti
Käydään mergeTwoLists([1,2,4], [1,3,4]) läpi: verrataan arvoja 1 ja 1 — valitaan l1(1) ja siirretään l1 kohtaan 2. Verrataan arvoja 2 ja 1 — valitaan l2(1) ja siirretään l2 kohtaan 3. Verrataan arvoja 2 ja 3 — valitaan l1(2) ja siirretään l1 kohtaan 4. Verrataan arvoja 4 ja 3 — valitaan l2(3) ja siirretään l2 kohtaan 4. Verrataan arvoja 4 ja 4 — valitaan l1(4) ja siirretään l1 kohtaan None. Liitetään jäljellä oleva l2(4). Tulos: [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]))Keskikohdan etsiminen hitaalla ja nopealla osoittimella
Jaa lista keskikohdasta käyttämällä hitaiden ja nopeiden osoittimien mallia. slow etenee yhden askeleen ja fast kaksi askelta. Kun fast saavuttaa arvon None (tai viimeisen solmun), slow on keskikohdassa. Parillisen pituisessa listassa tämä antaa kahdesta keskimmäisestä solmusta ensimmäisen, mikä on lomituslajittelussa tavanomainen valinta.
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]Lomituslajittelu linkitetyllä listalla
LeetCode 148 'Sort List': järjestä linkitetty lista ajassa O(n log n) ja käytä tilaa O(log n). Lähestymistapa on seuraava: jaa lista keskipisteestä, järjestä kumpikin puolisko rekursiivisesti ja yhdistä ne. Linkitetyn listan lomituslajittelu on luonteva ratkaisu, koska jakaminen keskipisteestä vie ajan O(n) (toisin kuin taulukoilla, joilla se vie ajan O(1)), mutta kokonaisaikavaativuus on silti O(n log n) ja pinoa tarvitaan vain O(log n) verran.
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]N:nnen solmun etsiminen lopusta
LeetCode 19 'Remove Nth Node From End of List': etsi n:s solmu lopusta yhdellä läpikäynnillä. Käytä kahta osoitinta, joiden välillä on täsmälleen n solmua. Siirrä fast-osoitinta n askelta slow-osoittimen edelle. Siirrä sitten molempia yhdessä, kunnes fast saavuttaa viimeisen solmun. Tällöin slow on lopusta laskettuna (n+1):nnessä solmussa eli poistettavan solmun edeltäjässä.
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]Miksi N:nnen solmun poistossa tarvitaan n+1 askelta
Keskeinen hienovaraisuus on siirtää fast-osoitinta dummy-solmusta n+1 askelta (ei n askelta). n+1 askeleen jälkeen fast on n+1 askelta slow-osoittimen edellä, sillä molemmat aloittivat dummystä. Kun fast saavuttaa None-arvon eli yhden askeleen pyrstön jälkeen, slow on n+1 paikkaa ennen None-arvoa. Tämä tarkoittaa, että slow on kohdassa (length - n - 1) nollasta alkavassa numeroinnissa eli kohdesolmun edeltäjässä. Näin lausekkeella slow.next = slow.next.next voidaan poistaa lopusta n:nnenä oleva solmu siististi.
# 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]')Kahden linkitetyn listan leikkauskohta
LeetCode 160 'Intersection of Two Linked Lists': etsi solmu, jossa kaksi listaa ensimmäisen kerran leikkaavat. O(1)-tilaa käyttävä temppu on siirtää kahta osoitinta, yhtä kummassakin listassa. Kun osoitin saavuttaa None-arvon, ohjaa se toisen listan alkuun. Enintään len(A) + len(B) askeleen jälkeen molemmat osoittimet ovat kulkeneet saman kokonaismatkan ja niiden täytyy olla leikkauskohdan solmussa (tai molemmat None-arvossa, jos leikkauskohtaa ei ole).
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) # 8K:n järjestetyn listan yhdistäminen (hajota ja hallitse)
LeetCode 23 'Merge K Sorted Lists': kun annettuna on k järjestettyä listaa, yhdistä ne yhdeksi listaksi. Optimaalinen lähestymistapa on yhdistää listoja pareittain hajota ja hallitse -menetelmällä, jolloin listojen määrä puolittuu jokaisella kierroksella. Kun listoja on k ja niiden keskimääräinen pituus on n, aikaa kuluu O(n k log k), kun taas peräkkäiseen yhdistämiseen kuluu O(n k²). Myös minimikeon käyttö vie ajan 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]Pariton–parillinen linkitetty lista
LeetCode 328 'Odd Even Linked List': ryhmittele ensin kaikki parittomilla indekseillä olevat solmut ja sitten parillisilla indekseillä olevat solmut (indeksointi alkaa yhdestä). Ylläpidä kahta erillistä ketjua, paritonta ja parillista, ja yhdistä ne lopuksi. Yksi listan läpikäynti riittää, joten aikavaativuus on O(n) ja tilavaativuus O(1). Tämä on selkeä esimerkki kahden osoittimen samanaikaisesta siirtämisestä eri askelpituuksilla.
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]Kaikki yhteen
Tämän oppitunnin kolme mallia — järjestettyjen listojen yhdistäminen, jakaminen keskipisteestä ja n:nnen solmun etsiminen lopusta — perustuvat samaan ajatukseen: seuraa sijainteja ylimääräisten osoitinmuuttujien avulla ilman lisämuistia. Dummy-alkusolmu yksinkertaistaa yhdistämistä ja poistamista, slow–fast-osoittimien välinen etäisyys kiinnittää tietyn suhteellisen sijainnin, ja yhden osoittimen siirtäminen ensin luo halutun etäisyyden.
Nimetkää haastattelussa käyttämänne malli ennen koodaamista: ”Käytän kahden osoittimen etäisyystekniikkaa löytääkseni lopusta n:nnen solmun yhdellä läpikäynnillä.” Tämä osoittaa jäsenneltyä ajattelua.
Pikatarkistus
Testaa tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -aiheiden ymmärtämisesi.
Oppitunnin kertaus
Tässä oppitunnissa opit, että kahden järjestetyn listan yhdistäminen käyttää dummy-alkusolmua ja vertailua jokaisella askeleella, jolloin aikavaativuus on O(n+m) ja tilavaativuus O(1), keskipisteestä jakaminen käyttää slow–fast-osoittimia, joista fast pysäytetään viimeiseen kelvolliseen pariin ja lopusta n:nnen solmun etsimisessä fast-osoitinta siirretään n+1 askelta eteenpäin, jotta slow päätyy edeltäjään. Seuraavaksi rakennetaan pinoja ja jonoja ja sovelletaan niitä klassisiin haastatteluongelmiin.
Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 90
- Oppitunnit
- 360
Usein kysytyt kysymykset
Onko oppitunti ”Yhdistäminen, jakaminen ja n:nnen alkion etsiminen lopusta” ilmainen?
Kyllä – oppitunnin ”Yhdistäminen, jakaminen ja n:nnen alkion etsiminen lopusta” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Yhdistäminen, jakaminen ja n:nnen alkion etsiminen lopusta”?
Yhdistäkää kaksi järjestettyä linkitettyä listaa ajassa O(n), jakakaa lista keskikohdasta hitaiden ja nopeiden osoittimien avulla ja etsikää n:s solmu hännästä lukien. Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 4/4.
Kuinka kauan ”Yhdistäminen, jakaminen ja n:nnen alkion etsiminen lopusta”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?
Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Node-luokka ja listan rakentaminen
- Linkitetyn listan kääntäminen
- Syklien tunnistaminen Floydin algoritmilla
- Yhdistäminen, jakaminen ja n:nnen alkion etsiminen lopusta