Saat saya mengerjakan LeetCode, saya menemukan masalah 141. Karena saya menggunakan JavaScript sebagai bahasa pemrograman utama saya, yang tidak memiliki struktur data Daftar Tertaut, saya kesulitan memahami idenya dan menemukan solusi. LeetCode memiliki implementasi Daftar Tertaut untuk JavaScript bawaan dan Anda hanya perlu menulis solusinya. Jadi saya berpikir, kenapa tidak mempermudah orang lain yang mungkin menghadapi masalah yang sama. Artikel ini dapat membantu Anda memahami beberapa konsep, jadi bacalah sampai akhir. Mari kita mulai dengan menanyakan pertanyaan yang jelas…
Apa itu Daftar Tertaut?
Daftar tertaut adalah struktur data linier yang mirip dengan array. Namun, tidak seperti array, elemen tidak disimpan di lokasi memori atau indeks tertentu. Sebaliknya setiap elemen adalah objek terpisah yang berisi pointer atau link ke objek berikutnya dalam daftar itu.
Setiap elemen (biasa disebut node) berisi dua item: data yang disimpan dan link ke node berikutnya. Data dapat berupa tipe data apa pun yang valid. Anda dapat melihatnya diilustrasikan pada diagram di bawah ini.
Dalam JavaScript, akan terlihat seperti ini:
const list = {
head: {
data: 6
next: {
data: 10
next: {
data: 12
next: {
data: 3
next: null
}
}
}
}
}
};
Seperti yang dinyatakan sebelumnya, node daftar berisi dua item: data dan penunjuk ke node berikutnya. Kita dapat mengimplementasikan kelas List Node dan Linked List dalam JavaScript sebagai berikut:
class ListNode {
constructor(data, next = null) {
this.data = data
this.next = next
}
}
class LinkedList {
constructor(head = null) {
this.head = head
}
}
Dengan menggunakan fungsi berikut, kita dapat mengubah array menjadi daftar tertaut.
function getLinkedList (arr){
const head = arr.reverse().reduce((a,b) => {
if (!a) {
a = new ListNode(b);
} else {
a = new ListNode(b, a);
}
return a;
}, null);
return new LinkedList(head);
}
Mari buat daftar tertaut dan akses node-nya.
const list = getLinkedList([2,5,1,7])
console.log(list.head)
// ListNode { data: 2, next: ListNode { data: 5, next: ListNode { data: 1, next: [ListNode] } }}
console.log(list.head.next.data)
// 5
Sekarang kami memiliki daftar tertaut dalam JavaScript. Namun, yang sebenarnya kita perlukan adalah daftar tertaut yang memiliki siklus.
Apa itu Siklus Daftar Tertaut?
Siklus terjadi ketikadaftar tertaut tidak lagi linier dengan awal dan akhir — melainkan berputar melalui perulangan node.
Kita dapat mencapai hal ini dengan mengarahkan node ekor berikutnya ke node lain dalam daftar. Katakanlah kita ingin siklus dimulai pada posisi 2, kita dapat mencapainya dengan melakukan…
let tail = head
// get the tail
while(tail.next) {
tail = tail.next
}
// get the cycle node
let pos = 2;
let cycleNode = head
while(pos > 0 && cycleNode.next) {
cycleNode = cycleNode.next
pos--
}
// point the next of tail to cycle node
tail.next = cycleNode;
Sekarang kita sudah mendapatkan daftar tertaut dengan sebuah siklus, kita akhirnya bisa mulai menyelesaikan masalah sebenarnya.
Kelinci dan Kura-kura
Masalah memeriksa siklus dalam daftar tertaut mungkin tampak menakutkan pada awalnya, namun dengan menggunakan algoritme Tortoise dan Kelinci Floyd masalah ini mudah untuk dipahami dan diselesaikan. Idenya adalah menggunakan penunjuk lambat yaitu “kura-kura” dan penunjuk cepat yaitu “kelinci”. Kura-kuraemulai dari posisi 0 dan kelinci mulai dari posisi 1. Jika kura-kura berpindah 1 tempat pada suatu waktu dan kelinci berpindah 2 tempat pada suatu waktu, mereka akhirnya bertemu di suatu tempat dalam satu siklus. Anda dapat menggambar setiap gerakan untuk memverifikasi.
Mari kita bayangkan sebuah siklus dalam daftar tertaut dengan panjang di mana ekor menunjuk ke simpul kedua dalam daftar.
Inilah algoritma yang perlu kita terapkan dalam JavaScript.
create a slow node pointer and a fast node pointer
while: two pointers exists and fast pointer has a next value
move the slow pointer by one node and fast pointer by two nodes
if: at any time, slow pointer equals fast pointer
linked list contains a cycle.
Kode JavaScript mengimplementasikan ini:
function hasCycle (head) {
// create 2 pointers
let slow = head;
let fast = head;
while(fast && fast.next){ // while pointers exist and fast pointer has a next value
fast = fast.next.next; // move fast pointer by two nodes
slow = slow.next; // move slow pointer by one node
if(fast === slow) return true; // linked list has a cycle
}
return false;
}
Dan itulah solusi kita untuk LeetCode 141.Masalah 142 adalah lanjutan dari masalah ini dan mengharuskan kita menemukan simpul tempat siklus dimulai.
Pemikiran awal Anda mungkin, mari kembalikan simpul tempat kelinci dan kura-kura bertemu. Namun seperti yang Anda lihat pada ilustrasi di atas, siklusnya dimulai di simpul kedua, sedangkan kelinci dan kura-kura bertemu di simpul ketiga. Jadi itu tidak akan berhasil.
Solusinya akan membutuhkan penunjuk ketiga. Setelah kita menemukan titik pertemuan kelinci dan kura-kura yaitu penunjuk cepat sama dengan penunjuk lambat, maka kita terus menggerakkan penunjuk lambat dan penunjuk ketiga sebanyak satu titik, dan pada akhirnya keduanya akan bertemu di tempat siklus dimulai. Algoritma yang perlu kita terapkan dalam JavaScript adalah sebagai berikut.
create a slow node pointer and a fast node pointer
while: two pointers exists and fast pointer has a next value
move the slow pointer by one node and fast pointer by two nodes
if: at any time, slow pointer equals fast pointer
stop
if: fast pointer has no next and slow pointer doesnot equals fast pointer
linked list doesn't contain a cycle
else:
while: slow pointer doesn't equal third pointer
move both slow pointer and third pointer by one node
slow pointer/third pointer is the node where linked list cycle starts.
Kode JavaScript:
function cycleNode (head) {
if(!head || !head.next) return null // head has no next value
// create 3 pointers
let fast = head;
let slow = head;
let start = head; // third pointer
while(fast && fast.next){ // while pointers exist and fast pointer has a next value
fast = fast.next.next; // move fast pointer by two nodes
slow = slow.next; // move slow pointer by one node
if(fast === slow) break; // stop if slow pointer equals fast pointer
}
if(slow !== fast) return null // linked list doesn't contain a cycle
while(start !== slow){ // while slow pointer doesn't equal third pointer
start = start.next; // move third pointer by one node
slow = slow.next; // move slow pointer by one node
}
return start; // where cycle starts
}
Sekarang kami memiliki solusi yang berhasil untuk kedua masalah kami. Semoga ini bisa membantu Anda.
Perdamaian.
