LeetCode 206 · Reverse Linked List · Easy

Bağlı Listeyi Ters Çevirmek

Çözümün her adımını burada izleyebilirsin. Bir liste seç, İleri'ye bas ya da Oynat'a tıkla; okların tek tek nasıl çevrildiğini ve prev, current, next değişkenlerinin nasıl ilerlediğini gör.

Fikir üç adımda

  1. 1

    Bağlı liste bir zincir

    Her node bir sayı (val) ve bir sonraki node'u gösteren bir ok (next) tutar. Elinde sadece ilk node (head) vardır. Son node'un oku null'ı gösterir.

  2. 2

    Okları tek tek geriye çevir

    Listeyi baştan sona gez ve her node'un okunu bir öncekine çevir. İlk node'un oku null'a döner, çünkü ters çevrilince o son node olur.

  3. 3

    Oku çevirmeden önce yolu sakla

    current.next'i değiştirdiğin anda listenin geri kalanına giden yol kopar. Bu yüzden önce next = current.next ile bir sonraki node'u saklarsın.

Adım adım izle

Liste (node'lar yerinde duruyor, sadece oklar değişiyor)

henüz çevrilmedi current oku çevrildi ✂bu adımda kopan bağ

Değişkenler

prev'den başlayıp okları takip edince (ters çevrilmiş kısım)
current'tan başlayıp okları takip edince (kalan kısım)

Kod (Solution.cs içindeki metot)

Neden O(1) bellek?

Her node'a bir kez uğruyoruz: O(n) zaman. Liste 5 node da olsa 5000 node da olsa sadece üç değişken kullanıyoruz (prev, current, next) ve hiç yeni node oluşturmuyoruz: O(1) bellek.