Агуулгыг алгасах

Флойдын холбоост жагсаалтын цикл олох алгоритм

Холбоост жагсаалт өгөгдсөн бөгөөд түүний эхлэх цэгийг толгой (head) гэж тэмдэглэсэн, мөн цикл байж ч болно, байхгүй ч байж болно. Жишээ нь:

Энд бид C цэг буюу циклийн эхлэх цэгийг олох хэрэгтэй.

Санал болгож буй алгоритм

Энэ алгоритмыг Флойдын циклийн алгоритм буюу Яст мэлхий ба туулайн алгоритм гэж нэрлэдэг. Циклийн эхлэх цэгийг олохын тулд бид цикл огт оршин байгаа эсэхийг олж мэдэх хэрэгтэй. Энэ нь хоёр алхмаас тогтоно: 1. Циклийн оршин тогтнолыг олж мэд. 2. Циклийн эхлэх цэгийг ол.

Алхам 1: Циклийн оршин тогтнол

  1. $slow$ ба $fast$ гэсэн хоёр заагч ав.
  2. Эхэндээ хоёул холбоост жагсаалтын толгой руу заана.
  3. $slow$ нэг удаад нэг алхам хөдөлнө.
  4. $fast$ нэг удаад хоёр алхам хөдөлнө. ($slow$ заагчаас хоёр дахин хурдан).
  5. Аль нэг нь (эсвэл хоёул) null-д хүрэхээс өмнө хэзээ нэгэн цагт нэг зангилаа руу зааж байгаа эсэхийг шалга.
  6. Хэрэв тэд аяныхаа хэзээ нэгэн цагт нэг зангилаа руу зааж байвал энэ нь холбоост жагсаалтад цикл үнэхээр оршин байгааг илтгэнэ.
  7. Хэрэв бид null авбал энэ нь холбоост жагсаалт циклгүй болохыг илтгэнэ.

Одоо бид холбоост жагсаалтад цикл байгаа эсэхийг олж мэдсэн тул дараагийн алхамд бид циклийн эхлэх цэг буюу C-г олох хэрэгтэй.

Алхам 2: Циклийн эхлэх цэг

  1. $slow$ заагчийг холбоост жагсаалтын толгой руу дахин тавь.
  2. Хоёр заагчийг нэг удаад нэг алхам хөдөлгө.
  3. Тэдний уулзах цэг нь циклийн эхлэх цэг байх болно.
// Presence of cycle
public boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;

    while(fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;
        if(slow==fast){
            return true;
        }
    }

    return false;
}

// Assuming there is a cycle present and slow and fast are point to their meeting point
slow = head;
while(slow!=fast){
    slow = slow.next;
    fast = fast.next;
}

return slow; // the starting point of the cycle.

Яагаад ажилладаг вэ

Алхам 1: Циклийн оршин тогтнол

$fast$ заагч $slow$-ээс хоёр дахин хурдан хөдөлж байгаа тул хэзээ нэгэн цагт $fast$ нь $slow$-ээс хоёр дахин их зай туулсан байна гэж хэлж болно. Мөн эдгээр хоёр заагчийн туулсан зайн ялгаа $1$-ээр нэмэгдэж байгааг дүгнэж болно. 

slow: 0 --> 1 --> 2 --> 3 --> 4 (distance covered)
fast: 0 --> 2 --> 4 --> 6 --> 8 (distance covered)
diff: 0 --> 1 --> 2 --> 3 --> 4 (difference between distance covered by both pointers)
Циклийн уртыг $L$ гэж, удаан заагч циклийн оролтод хүрэхэд шаардагдах алхмын тоог $a$ гэж тэмдэглэе. $k \cdot L \geq a$ байх эерэг бүхэл тоо $k$ ($k > 0$) оршин байна. Удаан заагч $k \cdot L$ алхам хөдөлж, хурдан заагч $2 \cdot k \cdot L$ алхам туулах үед хоёр заагч хоёул циклийн дотор орно. Энэ үед тэдний хооронд $k \cdot L$ зай байна. Циклийн урт $L$ хэвээр байгааг харгалзвал энэ нь тэд циклийн дотор нэг цэгт уулзаж, ингэснээр тааралдана гэсэн үг.

Алхам 2: Циклийн эхлэх цэг

Хоёр заагч циклийн дотор уулзах цэг хүртлээ туулсан зайг тооцоолж үзье.

$slowDist = a + xL + b$ , $x\ge0$

$fastDist = a + yL + b$ , $y\ge0$

  • $slowDist$ нь удаан заагчийн туулсан нийт зай.
  • $fastDist$ нь хурдан заагчийн туулсан нийт зай.
  • $a$ нь хоёр заагч циклд орохын тулд хийх шаардлагатай алхмын тоо.
  • $b$ нь C ба G хоорондын зай буюу циклийн эхлэх цэг ба хоёр заагчийн уулзах цэгийн хоорондын зай.
  • $x$ нь удаан заагч C-ээс эхэлж C-д дуусан циклийн дотор давтсан тоо.
  • $y$ нь хурдан заагч C-ээс эхэлж C-д дуусан циклийн дотор давтсан тоо.

$fastDist = 2 \cdot (slowDist)$

$a + yL + b = 2(a + xL + b)$

Томьёог бодоод бид:

$a=(y-2x)L-b$

энд $y-2x$ нь бүхэл тоо

Энэ нь үндсэндээ $a$ алхам нь циклд хэдэн бүтэн давталт хийж, $b$ алхам ухрахтай ижил гэсэн үг. Хурдан заагч аль хэдийн циклийн оролтоос $b$ алхам түрүүлж байгаа тул хэрэв хурдан заагч дахин $a$ алхам хөдөлбөл циклийн оролтод очно. Мөн бид удаан заагчийг холбоост жагсаалтын эхнээс эхлүүлсэн тул $a$ алхмын дараа энэ нь мөн циклийн оролтод очно. Тиймээс хэрэв тэд хоёул $a$ алхам хөдөлбөл хоёул циклийн оролтод уулзана.

Бодлогууд: