Linked List Cycle

Q: Apa kompleksitas waktu dan ruang dari Siklus Linked List?

Kedua pendekatan membutuhkan waktu O(n) . Menandai node yang sudah dikunjungi membutuhkan memori tambahan O(n) . Pointer cepat dan lambat Floyd membutuhkan O(1) : dua nomor node.

Q: Bisakah kamu mendeteksi siklus dengan menghitung langkah?

Dalam bentuk array ini, ya: list tanpa siklus mencapai -1 dalam n tautan, jadi menelusuri n tautan tanpa mencapai akhir membuktikan adanya siklus. List yang terdiri dari pointer tidak memberimu n , dan menghitung node terlebih dahulu tidak akan selesai jika ada siklus.

MudahPointer cepat dan lambat Linked list

+10

Linked list disimpan dalam array next: node i terhubung ke node next[i], dan -1 berarti list berakhir di sana. Head adalah node 0. Ikuti tautan dari head dan kembalikan true jika kamu kembali ke node yang sudah pernah kamu kunjungi, atau false jika kamu mencapai akhir. Node yang tidak pernah dicapai selama penelusuran tidak dihitung, meskipun node-node tersebut saling terhubung dalam perulangan.

Fungsi

hasCycle(next: integer-array) → boolean

nextinteger-array: tautan setiap node: next[i] adalah node setelah node i, atau -1
Mengembalikanboolean: true jika penelusuran dari simpul 0 mengunjungi kembali sebuah simpul, false jika mencapai -1

Batasan

1 ≤ next.length ≤ 10⁴
-1 ≤ next[i] ≤ next.length-1
Beberapa node dapat terhubung ke node yang sama, dan beberapa node mungkin tidak dapat dijangkau dari head.

Contoh

Input: next = [1, 2, 3, 1]
Output: true
Penjelasan: Penelusuran berjalan dari 0, 1, 2, 3 lalu kembali ke 1. Node 1 dikunjungi dua kali, jadi list memiliki siklus melalui node 1, 2, dan 3.

Input: next = [2, -1, 1]
Output: false
Penjelasan: Penelusuran berjalan melalui 0, 2, 1 lalu mencapai -1: tiga node yang berbeda lalu berakhir, jadi tidak ada siklus.

Input: next = [-1, 2, 1]
Output: false
Penjelasan: Node 0 terhubung ke -1, jadi list hanya memiliki satu node. Node 1 dan 2 saling terhubung dalam loop, tetapi penelusuran dari head tidak pernah mencapai keduanya.

Pertanyaan lanjutan

Bisakah kamu juga menemukan simpul tempat siklus dimulai, tetap dengan memori tambahan O(1)?

Petunjuk

Buka satu per satu. Setiap petunjuk mengungkap sedikit lebih banyak.

0 dari 3 dibuka

Solusi

List dengan siklus tidak pernah mencapai -1, jadi kamu tidak bisa menunggu sampai akhir. Mengingat setiap node yang dikunjungi akan mendeteksi perulangan dengan memori O(n). Pointer cepat dan lambat Floyd mendeteksinya dengan dua bilangan bulat, karena pointer yang bergerak dua kali lebih cepat pasti akan menyusul pointer lambat di dalam perulangan.

Tandai simpul yang kamu kunjungi

Intuisi

Berjalanlah dari node 0 dan tandai setiap node saat kamu meninggalkannya. Tiba di node yang sudah ditandai berarti perjalanan telah kembali, dan dari sana perjalanan akan berulang selamanya. Pada contoh 1, kamu menandai 0, 1, 2, dan 3, lalu node 3 terhubung ke node 1, yang sudah ditandai.

Node diberi nomor dari 0 sampai n-1, jadi array boolean sepanjang n berfungsi sebagai set yang menyimpan node yang sudah dikunjungi. Perjalanan berhenti dalam n langkah: waktu O(n) dan memori O(n) untuk tanda-tandanya.

Algoritma

Buat array boolean visited dengan panjang n, semuanya bernilai false.
Tetapkan node = 0.
Selama node bukan -1, kembalikan true jika visited[node] sudah bernilai true.
Jika tidak, tetapkan visited[node] dan pindah ke next[node].
Saat penelusuran mencapai -1, kembalikan false.

def hasCycle(next):
    visited = [False] * len(next)
    node = 0
    while node != -1:
        if visited[node]:
            return True  # back at a node already on the path
        visited[node] = True
        node = next[node]
    return False

Pointer cepat dan lambat (deteksi siklus Floyd)

Intuisi

slow mengikuti satu tautan setiap putaran dan fast mengikuti dua. Jika list berakhir, fast mencapai -1 lebih dulu. Jika ada siklus, fast memasukinya dan terus berputar sampai slow tiba.

Setelah keduanya berada dalam siklus, fast mendekati slow tepat satu node setiap putaran. Jaraknya berkurang satu setiap putaran, sehingga mencapai nol dan kedua pointer berada di node yang sama; keduanya tidak bisa melewati nol.

Pada contoh 1, setelah satu putaran slow berada di node 1 dan fast di node 2. Setelah dua putaran, slow berada di node 2 dan fast di node 1. Setelah tiga putaran, keduanya berada di node 3.

slow memasuki siklus dalam n putaran, dan keduanya bertemu sebelum slow menyelesaikan satu putaran penuh: waktu O(n), memori sebesar dua bilangan bulat.

Algoritma

Tetapkan slow = 0 dan fast = 0.
Selama fast bukan -1 dan next[fast] bukan -1, pindahkan slow satu tautan dan fast dua tautan.
Setelah setiap perpindahan, kembalikan true jika keduanya berada di node yang sama.
Saat perulangan berhenti, fast menemukan ujungnya: kembalikan false.

def hasCycle(next):
    slow = 0
    fast = 0
    # fast needs two links to move; if either is missing, the list ends.
    while fast != -1 and next[fast] != -1:
        slow = next[slow]
        fast = next[next[fast]]
        if slow == fast:
            return True
    return False

Jebakan dan kasus tepi

Memindahkan fast dua tautan tanpa memeriksa keduanya. fast dan next[fast] harus berupa node yang valid sebelum kamu membaca next[next[fast]]; jika tidak, kamu membaca next[-1], yang menyebabkan crash, atau di Python diam-diam membaca elemen terakhir.
Membandingkan pointer sebelum memindahkannya. Keduanya dimulai dari node 0, jadi pemeriksaan di awal perulangan melaporkan adanya siklus di setiap list.
Melihat seluruh array alih-alih lintasannya. Dalam [-1, 2, 1], node 1 dan 2 membentuk perulangan yang tidak dapat dijangkau dari head, jadi jawabannya adalah false. Nilai yang berulang juga bukan berarti ada siklus: dalam [4, 4, 4, 4, -1], empat node terhubung ke node 4.
Menganggap bahwa siklus harus kembali ke head. Dalam [1, 2, 3, 4, 4], node terakhir terhubung ke dirinya sendiri.

Pertanyaan yang sering diajukan4

Bagaimana cara kerja deteksi siklus Floyd?

Dua pointer dimulai dari head: satu bergerak satu link setiap langkah, yang lain dua. Jika tidak ada siklus, pointer yang bergerak cepat mencapai ujung. Jika ada siklus, keduanya akhirnya berada di dalamnya. Pointer yang bergerak cepat memperkecil jarak satu node setiap langkah, lalu keduanya bertemu di node yang sama.

Apa kompleksitas waktu dan ruang dari Siklus Linked List?

Kedua pendekatan membutuhkan waktu O(n). Menandai node yang sudah dikunjungi membutuhkan memori tambahan O(n). Pointer cepat dan lambat Floyd membutuhkan O(1): dua nomor node.

Bisakah kamu mendeteksi siklus dengan hash set?

Ya. Dalam list yang dibangun dari object, masukkan setiap referensi node ke dalam hash set dan laporkan adanya siklus jika referensi tersebut sudah ada di sana. Cara ini berjalan dalam waktu O(n), tetapi menggunakan memori O(n). Itulah sebabnya pewawancara biasanya menanyakan metode Floyd selanjutnya.

Bisakah kamu mendeteksi siklus dengan menghitung langkah?

Dalam bentuk array ini, ya: list tanpa siklus mencapai -1 dalam n tautan, jadi menelusuri n tautan tanpa mencapai akhir membuktikan adanya siklus. List yang terdiri dari pointer tidak memberimu n, dan menghitung node terlebih dahulu tidak akan selesai jika ada siklus.

def hasCycle(next):
    # Tulis kodemu di sini

Tes #1

Tes #2

Tes #3

Argumen

next = [1, 2, 3, 1]

Output yang diharapkan

true