Remove Nth Node From End of List
Aynı uzunluktaki iki dizide saklanan tek yönlü bağlı bir liste veriliyor. i düğümü values[i] değerini tutar ve next[i] düğümüne bağlanır; -1 listeyi sonlandırır ve baş düğüm 0'dır. Düğümler liste sırasına göre saklanmadığından bağlantıları izleyin.
Listenin sonundan başlayarak sayıldığında n. düğümü kaldırın; son düğüm sondan 1. düğümdür. Kalan düğümlerin değerlerini liste sırasına göre döndürün.
Fonksiyon
- valuesinteger-array
- her düğümün tuttuğu değer
- nextinteger-array
- Her düğümün bağlantı verdiği düğümün indeksi ya da son düğüm için -1
- ninteger
- sondan başlayarak sayıldığında, 1 son düğüm olmak üzere hangi düğümün kaldırılacağı
- Döndürürinteger-array
- kalan değerler liste sırasına göre, tek düğüm kaldırıldığında boş
Kısıtlar
1 ≤ L ≤ 5000; buradaL,valuesvenextdizilerinin uzunluğudur.-100 ≤ values[i] ≤ 1001 ≤ n ≤ L- Her
next[i],-1ya da0ileL-1arasında bir düğüm indeksidir. - Listenin
0düğümünden başlayarak her düğümü tam olarak bir kez ziyaret eder ve ardından-1değerine ulaşır. Döngü yoktur.
Örnekler
- Girdi
- values = [5, 9, 2, 7, 6]next = [2, 3, 4, -1, 1]n = 2
- Çıktı
- [5, 2, 6, 7]
- Açıklama
0düğümünden bağlantıları takip etmek0, 2, 4, 1, 3düğümlerini ziyaret eder; dolayısıyla liste5, 2, 6, 9, 7şeklindedir. Sondan 2. düğüm1, değeri ise9’dur ve bu düğüm olmadan liste5, 2, 6, 7şeklindedir.values[5-2] = 7dizi girdisi silinecek düğüm değil, son düğümdür.
- Girdi
- values = [10, 20, 30, 40]next = [1, 2, 3, -1]n = 4
- Çıktı
- [20, 30, 40]
- Açıklama
- Dört düğüm ve
n = 4: sondan 4. düğüm baştır. Liste artık1düğümünden başlar ve20, 30, 40şeklinde devam eder.
- Girdi
- values = [42]next = [-1]n = 1
- Çıktı
- []
- Açıklama
- Tek düğüm hem baş hem de son düğümdür. Onu kaldırmak listeyi boş bırakır; bu nedenle cevap
[]olur.
Gönderirken +14 gizli test
Ek soru
Düğümü önce uzunluğu saymadan tek geçişte bulup bağlantısını kesebilir misin?
İpuçları
Tek tek açın. Her biri biraz daha fazlasını gösterir.
Bir liste yalnızca ileri doğru ilerler ve düğüm, sondan olan uzaklığıyla tanımlanır. Uzunluğunu
Lbilseydin, önden kaçıncı sırada olurdu? Ve onu listeden çıkarmak için hangi düğümün bağlantısını değiştirmen gerekir?Uzunluğu bilmeden sona olan mesafeyi ölçebilirsin. Bir işaretçiyi diğerinin
nbağlantı önünde başlat ve ikisini birlikte ilerlet. Öndeki son düğümde durduğunda, takip eden kaldırılacak düğümün hemen önünde olur.fastişaretçisininkez ileri taşı. Artık-1ise baş düğüm silinecek düğümdür; bu nedenle listenext[0]noktasından başlar. Aksi takdirde,next[fast] != -1ikenslowvefastişaretçilerini birlikte ilerlet, ardındannext[slow] = next[next[slow]]olarak ayarla. Baş düğümden başlayarak listeyi dolaş ve değerleri topla.
Çözüm
Hedef, sondan olan uzaklığıyla tanımlanır; ancak tek yönlü bağlı bir listede yalnızca ileri gidebilirsin ve sonun nerede olduğunu ancak oraya ulaştığında öğrenirsin. Bir düğümü kaldırmak için de ondan önceki düğümde olman gerekir; çünkü değişen bağlantı o düğüme aittir. Listeyi bir diziye kopyalayabilir ya da düğüm sayısını bulup tekrar ilerleyebilirsin. Klasik çözüm, aralarında n bağlantı bulunan iki işaretçi kullanır; böylece öndeki işaretçi son düğüme ulaştığında, arkadaki hedef düğümün hemen önünde olur. Aşağıda L, düğüm sayısıdır.
Dizileri bir diziye kopyalayın
Sezgi
Bu problemde bir işaretçi, düğüm indeksidir. İleri gitmek için node = next[node] kullanılır ve -1 değerine ulaşmak listenin sonunu geçtiğiniz anlamına gelir. İlk örnekte, 0 düğümünden başlayan yürüyüş 0 → 2 → 4 → 1 → 3 → -1 şeklindedir.
Sondan saymak yalnızca bir listenin konumları olmadığı için zordur. Öyleyse listeye konumlar verin: bir kez yürüyün ve her değeri bir diziye ekleyin. İlk örnekte bu dizi [5, 2, 6, 9, 7] olur. L değer içeren bir dizide sonuncusu L-1 indeksinde bulunur; bu nedenle sondan n'inci değer L-n indeksindedir. Burada bu, 5-2 = 3, yani 9 değeridir. Bu değeri silin ve [5, 2, 6, 7] döndürün.
Bu yöntem doğrudur ve O(L) zamanda çalışır; ancak listenin tamamını kopyalar ve hiçbir bağlantıya dokunmaz. Problemin amacı, sonraki iki yaklaşımın yaptığı gibi listeyi doğrudan düzenlemek ve O(1) ek bellek kullanmaktır.
Algoritma
- Boş bir diziyle ve
node = 0ile başlayın. node,-1olmadığı sürecevalues[node]değerini ekleyin venext[node]değerine geçin.length - nindeksindeki girdiyi silin.- Diziyi döndürün.
def removeNthFromEnd(values, next, n):
# Write the values out in list order.
order = []
node = 0
while node != -1:
order.append(values[node])
node = next[node]
# Counting from the end, the n-th value sits at index len(order) - n.
del order[len(order) - n]
return orderDüğümleri say, sonra bağlantılarını kaldır
Sezgi
Bir düğümü listeden çıkarmak için, ondan önceki düğümün bağlantısını değiştirerek aradaki düğümü atlamasını sağlarsın: next[prev] = next[next[prev]]. Çıkarılan düğüm dizilerde hâlâ bulunur, ancak baştan başlayan hiçbir gezinme artık ona ulaşmaz.
Öyleyse prev değerini bul. İlk gezinmede düğümleri say. Başı 0 konumu olarak sayarsak hedef, L-n konumunda; ondan önceki düğüm ise L-n-1 konumundadır. Bu düğüme baştan L-n-1 adımda ulaşırsın. İlk örnekte L = 5 ve n = 2: iki adım 0 → 2 → 4 seni 4 düğümüne götürür; bu düğüm, 9 olan 1 düğümüne bağlanır. next[4] = next[1] = 3 ayarı, listenin 5, 2, 6, 7 şeklinde olmasını sağlar.
Hedefin önünde hiçbir düğüm bulunmayan bir durum vardır: hedef baş olduğunda n = L. Bu durumda bağlantıları değiştirmek gerekmez. İkinci örnekte olduğu gibi, liste 0 yerine next[0] konumundan başlar. Ardından yanıtı toplamak için baştan ilerle. Liste üzerinde iki kez gezinmek yaklaşık 2L adım sürer ve yanıt dışında yalnızca birkaç tam sayı kadar bellek gerekir.
Algoritma
0düğümünden-1düğümüne kadar ilerleyin ve düğümleriLolarak sayın.n == Lise yeni başnext[0]olur.- Aksi hâlde
prevdeğerini0düğümünde başlatın veL-n-1kez ilerletin, ardındannext[prev] = next[next[prev]]olarak ayarlayın. - Baştan başlayarak ilerleyin ve
values[node]değerlerini sırayla toplayın.
def removeNthFromEnd(values, next, n):
# First pass: count the nodes.
length = 0
node = 0
while node != -1:
length += 1
node = next[node]
head = 0
if n == length:
# The node to remove is the head, so the list starts at its second node.
head = next[0]
else:
# Second pass: stop on the node just before position length - n.
prev = 0
for _ in range(length - n - 1):
prev = next[prev]
next[prev] = next[next[prev]] # skip over the removed node
result = []
node = head
while node != -1:
result.append(values[node])
node = next[node]
return resultn bağlantı aralıklı iki işaretçi
Sezgi
L'yi bilmeden "sondan n" ölçebilirsin. slow başta beklerken fast'i n bağlantı ilerlet. Sonra ikisini de her seferinde bir bağlantı ilerlet. Aradaki mesafe n olarak kalır; bu yüzden fast son düğümde durduğunda (next[fast] == -1, konum L-1), slow L-1-n konumunda, yani hedef düğümden hemen önceki düğümde durur. Tek bir next[slow] = next[next[slow]] işlemi hedefi çıkarır.
İlk örneği takip et. fast iki adım atar: 0 → 2 → 4. Şimdi ikisi de ilerler: slow 2'ye giderken fast 1'e gider, ardından slow 4'e giderken fast 3'e gider. 3 numaralı düğüm son düğümdür, bu yüzden durursun. next[4], 9 olan 1 numaralı düğümdür ve next[4] = next[1] = 3 olarak ayarlamak onu kaldırır.
Baş düğüm durumu kendiliğinden ortaya çıkar. n ≤ L olduğundan, fast başlangıçta ilerlerken yalnızca n = L olduğunda -1'e ulaşır; hedefin baş düğüm olduğu durum da tam olarak budur. Düğüm nesneleriyle çalışırken bu durumu ortadan kaldırmak için baş düğümün önüne bir sahte düğüm koyabilirsin; burada fast == -1 kontrolü aynı işi görür. Bulma ve bağlantıyı kesme tek geçişte yapılır. Yanıtı yazdırmak için bir geçiş daha gerekir; bu, her yaklaşımın ihtiyaç duyduğu bir adımdır.
Algoritma
-
fast = 0olarak ayarla vefast = next[fast]ilenkez ilerlet. fast == -1ise, hedef baş düğümdür: yeni başnext[0]olur.- Aksi takdirde
slow = 0olarak ayarla venext[fast] != -1iken ikisini de ilerlet. next[slow] = next[next[slow]]olarak ayarla.- Baştan başlayarak ilerle ve
values[node]değerlerini sırayla topla.
def removeNthFromEnd(values, next, n):
# Send fast n links ahead of slow.
fast = 0
for _ in range(n):
fast = next[fast]
head = 0
if fast == -1:
# Fast fell off the end, so the list has exactly n nodes: remove the head.
head = next[0]
else:
# Move both, keeping the gap. When fast stands on the last node,
# slow stands just before the node to remove.
slow = 0
while next[fast] != -1:
slow = next[slow]
fast = next[fast]
next[slow] = next[next[slow]] # skip over the removed node
result = []
node = head
while node != -1:
result.append(values[node])
node = next[node]
return result
Tuzaklar ve uç durumlar
Yanlış yanıtların çoğu, takipçinin nerede durduğundan ve baş düğümün kaldırıldığı durumdan kaynaklanır.
- Dizi indeksindeki
L-ngirdisini kaldırmak. Düğümler listedeki sıraya göre saklanmaz, bu nedenle bu indeks genellikle başka bir düğüme karşılık gelir. İlk örnektevalues[3] = 7son düğümdür,9değildir. next[fast] == -1koşulunda durmak yerinefast == -1koşulunda durmak. Bu,slowişaretçisini bir adım fazla ilerletip doğrudan hedef düğüme taşır; tek bağlı listede bir düğümün bağlantısını yine o düğümün kendisinden kesemezsiniz.- Baş düğüm durumunu unutmak.
n = Lolduğunda, baştan başladıktan sonrafastdeğeri-1olur venext[fast]okumak çoğu dilde çökmeye neden olur. Python,next[-1]ifadesini şikâyet etmeden okur ve yanlış bir liste döndürür; bunu fark etmek daha zordur. - Bağlantıyı
next[slow] = next[slow] + 1veyaslow + 2ile kesmek. Listedeki komşu düğümler dizilerde komşu değildir; hedef düğümden sonraki düğüme ulaşmanın tek yolunext[next[slow]]ifadesidir. - Baş düğüm kaldırıldıktan sonra yanıtı 0 numaralı düğümden başlayarak toplamak. Son yürüyüşe yeni baş düğümden başlayın.
- Dizilerin 1'den başladığı Lua ve R'deki ofseti unutmak. Düğüm indekslerini 0 tabanlı tutun ve
next[node + 1]okuyun. Ruby ve R,nextsözcüğünü ayırdığından, bu diller için başlangıç kodlarında parametreyenext_adı verilir.
Sıkça sorulan sorular4
Sondan n'inci düğümü bağlı listeden tek geçişte nasıl kaldırırsınız?
Aralarında n düğümlük mesafe olan iki işaretçi kullanın. İlkini n düğüm ileri taşıyın, ardından ilki son düğüme ulaşana kadar ikisini birlikte ilerletin. İkinci işaretçi artık kaldırılacak düğümün hemen önündedir; bu nedenle bağlantısını o düğümün ötesini gösterecek şekilde ayarlayın. İlk işaretçi önden ilerlerken listenin sonunu aşarsa kaldırılacak düğüm baş düğümdür.
Bu probleme yönelik çözümlerde neden sahte bir düğüm kullanılıyor?
Bir düğümü kaldırmak, ondan önceki düğümün bağlantısını değiştirmek anlamına gelir ve baş düğümün önünde başka bir düğüm yoktur. Baş düğümün önüne yerleştirilen bir sahte düğüm, baş düğüm de dâhil olmak üzere her düğümün bir önceki düğümü olmasını sağlar; böylece tek bir bağlantıyı kesme satırı tüm durumları kapsar. Ardından yanıt, sahte düğümün sonraki düğümünden başlar. n adım sonra öndeki işaretçinin listenin sonuna gelip gelmediğini kontrol etmek, ek düğüme gerek kalmadan aynı durumu ele alır.
Son düğümü sondan n'inci konumdan kaldırmanın zaman ve alan karmaşıklığı nedir?
L düğümden oluşan bir liste için, hedefin nerede olduğunu öğrenmek üzere listenin sonuna ulaşmanız gerektiğinden O(L) zaman gerekir. Önce sayma ve iki işaretçi yöntemi, her ikisi de O(1) ek bellek kullanır. Değerleri bir diziye kopyalamak O(L) bellek kullanır.
İki işaretçili çözüm, önce uzunluğu saymaktan daha mı hızlı?
Pek değil: ikisi de O(L) karmaşıklığındadır ve iki işaretçi birlikte hâlâ iki yürüyüşün yapacağı kadar hareket eder. Asıl kazanç, uzunluğu önceden bilmenizin gerekmemesidir; böylece yöntem, yalnızca bir kez okuyabileceğiniz bir akış olarak gelen listelerde de işe yarar. Görüşmecilerin genellikle istediği şey bu tek geçiştir.
Benzer problemler
Aynı fikirleri kullanan problemler. İki üçünü çözmek bir kalıbı kalıcı hale getirir.
Python
def removeNthFromEnd(values, next, n):
# Kodu buraya yazınDurum 1
Durum 2
Durum 3
Girdi
values = [5, 9, 2, 7, 6] next = [2, 3, 4, -1, 1] n = 2
Beklenen
[5, 2, 6, 7]