อ่านบทความนี้ใน Facebook
“ถ้าคุณเดินอยู่ในสวนแห่งหนึ่ง คุณจะรู้ได้อย่างไรว่าถ้าคุณเดินไปเรื่อย ๆ คุณจะไม่เดินเป็นวงกลม?”
วิธีการที่ง่ายที่สุดก็คงจะเป็นการที่เราเดินไปเรื่อย ๆ จากนั้นก็จด landmark ระหว่างทางไว้ (หรืออาจจะทำเครื่องหมายไว้) ว่าเราเดินผ่านตรงไหนแล้ว
วิธีการดังกล่าวเปรียบได้กับการที่เราสร้าง pointer ขึ้นมาตัวนึงที่จะเดินไปเรื่อย ๆ ใน linked list จากนั้นสร้างตัวแปรอีกตัวเพื่อเก็บ visited ว่าจดไว้ว่าเราเคยเดินผ่าน node ไหนไปแล้วบ้าง …ถ้าหากว่าเราเจอ node ที่เคย visit ไปแล้วก็แสดงว่ามี cycle นั่นเอง
สำหรับวิธีการดังกล่าวจะเห็นว่าเราจำเป็นต้องสร้างตัวแปรขึ้นมาเพื่อเก็บค่าเพิ่ม (space complexity \(O(n)\)) …คำถามก็คือถ้าหากว่าเราไม่อยากเก็บข้อมูลอะไรเพิ่มเลยหละ เราจะทำอย่างไร?
วิธีการนึงที่เราสามารถทำได้ก็คือ “เอากระต่ายกับเต่า มาปล่อยให้มันเดินไปเรื่อย ๆ ครับ” (อาจจะทำเครื่องติดไว้ว่า ถ้าเต่ากับกระต่ายวิ่งอยู่ในตำแหน่งเดียวกันให้ส่งสัญญาน BEEEP! มาที่คุณ)
กระต่ายวิ่งเร็วกว่าเต่า 2 เท่า …คำถามก็คือ “ถ้าหากว่าเราปล่อยเต่ากับกระต่ายวิ่งไปเรื่อย ๆ ใน park ที่มี cycle สิ่งที่จะเกิดขึ้นคืออะไร?”
ถ้าหากว่า park ไม่มี cycle แน่นอนว่าเต่าก็จะวิ่งไปเรื่อย ๆ และไม่มีทางที่จะวิ่งทันกระต่ายได้เลย (เพราะมันวิ่งช้ากว่า)
แต่ถ้าหากว่า park มี cycle ถึงแม้ว่ากระต่ายจะวิ่งเร็วกว่า แต่ถึงจุดนึงมันจะวิ่งวน ๆ สุดท้ายมันจะต้องมีจุดนึงที่เต่าวิ่งผ่านกระต่าย และคุณจะได้สัญญาน BEEEP! กลับมาแน่นอน (หรือลองคิดตอนที่วิ่งในสนามวิ่งก็ได้ มันจะมีเพื่อนบางคนที่วิ่งผ่านเราไปแล้ว 2-3 รอบ ทั้ง ๆ ที่เราวิ่งไม่จบรอบเลย 😆)
วิธีการดังกล่าวคือเทคนิคที่เรียกว่า two pointers ครับโดยมี fast pointer (กระต่าย) ที่จะเดินไปทีละ 2 node กับ slow pointer (เต่า) ที่จะเดินไปทีละ node ในแต่ละ iteration
จะเห็นว่าวิธีการดังกล่าวเราไม่จำเป็นต้องเก็บข้อมูลอะไรเพิ่มเลย เพียงแต่ว่าปล่อยให้มันรันไปเรื่อย ๆ จนกระทั่ง 1. กระต่ายวิ่งไปสิ้นสุด list แล้ว (ไม่มี cycle) หรือ 2. กระต่ายกับเต่าวิ่งมาเจอกันอีกรอบ (มี cycle)
อย่างไรก็ตามเราก็คงอยากจะรู้ใช่ไหมหละครับว่า “แล้ว cycle มันเริ่มที่ตรงไหน?”
สำหรับ algorithm ที่ใช้หา node ที่เป็นจุดเริ่มต้นของ cycle คือ algorithm ที่เรียกว่า “Floyd’s cycle detection algorithm” ครับ
แต่เนื่องจากโพสนี้จะยาวเกินไป ไว้เราจะเขียนอธิบายแยกใน EP หน้าอีกทีว่า “เราจะใช้เต่าและกระต่ายในการหา node ที่เป็นจุดเริ่มต้นของ cycle” ได้อย่างไร
สุดท้ายนี้เราขอทิ้งคำถามชวนคิดไว้ประมาณนี้ว่า “มีโอกาสไหมที่ fast pointer จะกระโดดข้าม slow pointer โดยที่ไม่เจอกันเลย ใน linked list ที่มี cycle?” อยากชวนมาแชร์กันว่ามีหรือไม่มี และเพราะอะไร
