อ่านบทความนี้ใน Facebook
ใน EP ที่แล้วเราได้ใช้เทคนิค two pointers (กระต่ายและเต่า) ในการ detect ไปแล้วว่า linked list ดังกล่าวมี cycle หรือไม่ …แต่ก็มีคำถามทิ้งท้ายไว้ว่า “เราจะสามารถหา node เป็นจุดเริ่มต้นของ cycle ได้ไหม”
ขอแนะนำให้รู้จักกับ Floyd’s cycle-finding algorithm ครับ โดยเขากล่าวไว้ว่า
- เต่าจะเดินที่ละก้าว ส่วนกระต่ายจะเดินทีละ 2 ก้าวในแต่ละครั้ง
- ถ้า linked list มี cycle: เมื่อเราปล่อยเต่าและกระต่ายเดินไปเรื่อย ๆ มันจะไปเจอกันที่ node ใด node หนึ่งใน cycle (จากนั้นหยุดเดินไว้ที่ตรงนี้ก่อน)
- หยิบเต่าไปไว้ที่จุดแรกสุด และเปลี่ยนความเร็วของกระต่ายให้เท่ากับเต่า (เดินทีละก้าวเหมือนกัน) “เมื่อปล่อยมันเดินไปเรื่อย ๆ ทั้งสองจะมาเจอกันที่จุดเริ่มต้นของ cycle พอดี”
ลองกดเล่น interactive ด้านล่างได้เลยครับ ⤵
DAMNN!! ฟังดูเป็นอะไรที่ magical มากใช่ไหมหละครับ แบบทำไมอยู่ ๆ เต่ากับกระต่ายถึงเดินมาเจอกันในจุดที่เรากำลังตามหาซะงั้น ทำไมมันถึงทำงานได้ถูกต้อง?
โพสนี้จะชวนมาหาคำตอบกันครับ ผ่านรูปและหลักเหตุและผลแบบง่าย ๆ (ส่วน proof ที่เป็นคณิตศาสตร์เราเชื่อว่าถ้าเข้าใจหลักการแล้ว อ่านต่อเองเข้าใจแน่นอน)
“มีโอกาสไหมที่ fast pointer จะกระโดดข้าม slow pointer โดยที่ไม่เจอกันเลย ใน linked list ที่มี cycle?”
คำตอบก็คือไม่มีครับ เพราะจะเห็นว่า gap ระหว่างกระต่ายกับเต่าจะลดลงทีละ 1 เรื่อย ๆ จนกระทั้ง gap เหลือ 0 หรือทั้งสองมาเจอกัน (นอกจากนี้จะเห็นว่าถ้า gap ในตอนแรกคือ 3; ตำแหน่งที่เต่าและกระต่ายจะเจอกันก็คือ จุดเริ่มต้นของเต่า + 3 นั่นเอง ไว้สำหรับคำนวนง่าย ๆ)
ข้อสรุป 1: “ถ้าหากว่ากระต่ายตามเต่าอยู่ G step (gap) ตำแหน่งที่เต่าจะเจอกับกระต่ายก็คือ ตำแหน่งของเต่า + G”
นอกจากนี้ ถ้าหากว่าเรากำหนดตัวแปรขึ้นมา 3 ตัว (ดูรูปปกประกอบ) ได้แก่:
- L แทนระยะทางของจุดเริ่มต้นถึงจุด start cycle (มีค่า 8 เพราะเต่าจะก้าว 8 ครั้งนับจากจุดเริ่มต้นถึงจะไปถึงจุด start cycle)
- K แทนระยะทางของกระต่ายเทียบกับ start cycle เมื่อเต่าเดินไปถึงจุด start cycle (ลองเช็คจาก interactive ด้านบนดู)
- ส่วน C แทนระยะทางจากจุด start cycle เดินไปเรื่อย ๆ จนกลับมาที่เดิม
เรามาลองคิดกันเล่น ๆ ว่า “เมื่อเต่าอยู่ที่จุด start cycle กระต่ายจะเดินไปทั้งหมดกี่ก้าว?”
…ถ้าเต่าเดินไป L ก้าวและกระต่ายเดินเร็วกว่า 2 เท่า นั่นก็หมายความว่า “กระต่ายจะเดินไปทั้งหมด 2L ก้าว และเดินไปจบที่ node ที่เลยจาก start cycle มา K ก้าว”
ใน 2L ก้าวนั้นจะเห็นว่า L ก้าวแรกมันคือระยะจากจุดเริ่มต้นถึง start cycle ดังนั้นถ้าหากว่าเราตัด L ก้าวนี้ออกไป เราก็จะได้ข้อสรุปว่า
ข้อสรุป 2: “ถ้าเราเดิน L ก้าวจากจุด start cycle เราจะเดินวนไปเรื่อย ๆ และเดินไปจบที่ node ที่เลยจาก start cycle มา K ก้าว”
เราไม่สนว่าจะวนกี่รอบ อาจจะ 0 รอบหรือ 1,2,3 รอบก็ได้ เพราะสุดท้ายมันจะวนกลับมาที่เดิม เราสนแค่ว่ามันจะเลยมา K ก้าวก็พอ
ณ จุดนี้จะเห็นว่ากระต่ายจะตามเต่าอยู่ 4 ก้าว (\(G = C - K = 4\)) ถ้าปล่อยมันเดินไปเรื่อย ๆ เต่าก็จะเจอกับกระต่ายในจุด \(C - K\) นั่นเอง
คำถามคือจากตำแหน่งที่ “C - K” เราต้องเดินอีกกี่ก้าวถึงจะถึงจุด start cycle? …คำตอบก็คือ อีก K ก้าวใช่ไหมหละครับ เพราะถ้าเดินอีก K ก้าวเราก็จะครบ cycle พอดี
“แล้วเราจะเดินอีก K ก้าวได้อย่างไร?”
ยังจำ “ข้อสรุปที่ 2” ได้ไหมหละครับ …ถ้าหากว่าเดิน L ก้าว เราจะเดินวนกลับมาที่เดิม (ซึ่งเราไม่สนใจอยู่แล้วว่าจะวนกลับมากี่ครั้ง) และเราจะเดินเลยจุดเริ่มต้นไปอีก K ก้าว!!
ดังนั้นเพียงแค่เราเดินไปอีก L ก้าว เราก็จะเดินไปถึง start cycle node ได้
สุดท้ายถามว่าทำยังไงหละถึงจะเดิน L ก้าว? “ก็จับเต่าโยนกลับไปที่จุดเริ่มต้นอีกครั้งแล้วปรับความเร็วของกระต่ายให้เท่ากับเต่าไงครับ”
เพราะเมื่อเต่ามันเดินได้ L รอบเมื่อไหร่ เต่าและกระต่ายก็จะอยู่ในจุด start cycle พอดี
