้พ่กจ๏ผLinked List๏ผ ๆฏ้่ฟๆ้ๅฐไธไธชไธไธช Node ้พๆฅๅจไธ่ตท็ๆฐๆฎ็ปๆ๏ผ้่ฟไธๅพๅฏไปฅ็ด่งๆๅ๏ผ
โโโโโโโโโ โโโโโโโโโ โโโโโโโโโ โโโโโโโโโ
โ Node โ โ Node โ โ Node โ โ Node โ
โ-------โ โ-------โ โ-------โ โ-------โ
โ Data โ โ Data โ โ Data โ โ Data โ
โ โ โ โ โ โ โ โ
โ Next ----> โ Next ----> โ Next ----> โ None โ
โโโโโโโโโ โโโโโโโโโ โโโโโโโโโ โโโโโโโโโ
Head Node1 Node2 Tail้พ่กจ็ฑ Node ็ปๆ๏ผ ๆฏไธช Node ๅ ๅซไธค้จๅ๏ผๆฐๆฎ (data) ไธๆๅไธไธ่็น็ๆ้ (Next) ใ
้พ่กจๅจ็ๆไนๅๆไปฌๅช้ไฟๅญไธไธชๆๅ Head ่็น็ๆ้๏ผๅ ถไป่็น้่ฆ้ ๆ้้ๅๆฅ่ฎฟ้ฎ๏ผ่ฟๅฏผ่ด้พ่กจ็่ฎฟ้ฎๆถ้ดๅคๆๅบฆไธบ ๏ผไฝๆๅ ฅๅ ้คๆไฝ็ๆถ้ดๅคๆๅบฆไธบ ใ
Tip
้พ่กจๅค็ไธญๅธธ็จๆๅทง
Dummy Head
ไนๆๅซๅจๅ
ตๆๅทง็๏ผๅฐฑๆฏๅจๅค็้พ่กจ็่ฟ็จไธญๅจ้พ่กจ็ Head ไนๅๅๅ ๅ
ฅไธไธช่็น Dummy Head๏ผๆๅ Head๏ผๅจๅค็ๅฎไนๅ็ดๆฅไฝฟ็จ dummy.next ๅฐฑ่ฝๆฟๅฐๆๆฐ็ head๏ผไธ็จๅจๅค็็่ฟ็จไธญไธ็ด่ฟฝ่ธช head ๅจๅชๅฟใ
dummy -> elem1(head) -> elem2 -> nil
ๅฟซๆ ขๆ้
็จไบๆพๅฏป้พ่กจ็ไธญ็นๆ้ช่ฏ้พ่กจไธญๆฏๅฆๅญๅจ็ฏ๏ผ่ฎพ็ฝฎไธคไธชๆ้ slow ๅ fast, slowๆฏๆฌก็งปๅจไธๆญฅ๏ผ fast ๆฏๆฌก็งปๅจไธคๆญฅ๏ผ่ฟๆ ทๅฝ fast ็งปๅจๅฐ้ๅฐพๆถ๏ผslow ๅๅฅฝ็งปๅจๅฐไธญ็น็ๅ
็ด ใ
- ๅฏนไบๅฅๆฐ้ฟๅบฆ็้พ่กจ๏ผ
slowๆๅๆๅ็ๅ ็ด ไธบ . - ๅฏนไบๅถๆฐ้ฟๅบฆ็้พ่กจ๏ผ
slowๆๅๆๅ็ๅ ็ด ไธบ .
ๆ ่ฎบๆฏๅฅๆฐ่ฟๆฏๅถๆฐ๏ผๅณๅ้จๅ็ head ้ฝไธบ slow.nextใ