Phát hiện chu kỳ trong danh sách được liên kết với cách tiếp cận Thỏ và Rùa

Question

Tôi hiểu rằng để phát hiện một chu trình trong danh sách được liên kết, tôi có thể sử dụng phương pháp Tiếp cận Thỏ và Rùa, có 2 con trỏ (con trỏ chậm và nhanh). Tuy nhiên, sau khi đọc trong wiki và các nguồn lực khác, tôi không hiểu tại sao nó được đảm bảo rằng hai con trỏ sẽ gặp nhau trong độ phức tạp thời gian O (n).

Answer 1

Đây là một nỗ lực bằng chứng không chính thức.

Hình dạng của chu kỳ không quan trọng. Nó có thể có một cái đuôi dài, và một vòng lặp về phía cuối, hoặc chỉ là một vòng lặp từ đầu đến cuối mà không có đuôi. Không phân biệt hình dạng của chu kỳ, có một điều rõ ràng - rằng con trỏ con rùa không thể bắt kịp con trỏ thỏ. Nếu hai đã từng gặp nhau, con trỏ thỏ phải bắt kịp con trỏ con rùa từ phía sau.

Với thành lập, hãy xem xét hai possibilites:

1. con trỏ thỏ là một bước phía sau con trỏ rùa.
2. con trỏ thỏ là hai bước sau con trỏ con rùa.

Tất cả khoảng cách lớn hơn sẽ giảm xuống một hoặc hai cuối cùng.

Giả sử con trỏ rùa luôn luôn di chuyển đầu tiên (có thể là cách khác xung quanh quá), sau đó trong trường hợp đầu tiên, con trỏ con rùa mất một bước về phía trước. Bây giờ khoảng cách giữa chúng là 2. Khi con trỏ thỏ mất 2 bước bây giờ, chúng sẽ hạ cánh trên cùng một nút. Đây là điều tương tự được minh họa để hiểu rõ hơn. Quá nhiều văn bản có thể cản trở.

 
♛ = hare 
♙ = tortoise 
X = both meet 

..♛♙... #1 - Initially, the hare is one step behind the tortoise. 
..♛.♙.. #2 - Now the tortoise takes one step. now hare is two steps behind. 
....X.. #3 - Next, the hare takes two steps and they meet! 

Bây giờ hãy xem xét trường hợp thứ hai khoảng cách giữa chúng là 2. Con trỏ chậm di chuyển một bước về phía trước và khoảng cách giữa chúng trở thành 3. Tiếp theo, con trỏ nhanh di chuyển về phía trước hai bước và khoảng cách giữa chúng giảm xuống 1 giống hệt với trường hợp đầu tiên mà chúng tôi đã chứng minh rằng chúng sẽ gặp trong một bước nữa. Một lần nữa, minh họa cho sự hiểu biết dễ dàng hơn.

 
.♛.♙... #1 - Initially, the hare is two steps behind the tortoise. 
.♛..♙.. #2 - Now the tortoise takes one step and they become three steps apart. 
...♛♙.. #3 - Next, the hare takes two steps which is identical to previous case. 

Bây giờ, là tại sao thuật toán này là đảm bảo được trong thời gian O (n), sử dụng những gì chúng tôi đã thành lập mà thỏ sẽ đáp ứng rùa trước khi nó di chuyển về phía trước. Điều đó có nghĩa là khi cả hai đều ở trong vòng lặp, trước khi con rùa hoàn thành một vòng khác, nó sẽ gặp thỏ khi con thỏ di chuyển nhanh gấp hai lần. Trong trường hợp xấu nhất, vòng lặp sẽ là một vòng tròn với các nút n. Trong khi con rùa chỉ có thể hoàn thành một vòng trong n bước, thỏ có thể hoàn thành hai vòng trong thời gian đó. Ngay cả khi con thỏ bị mất con rùa trong vòng đầu tiên của nó (mà nó sẽ), nó chắc chắn sẽ bắt kịp với con rùa ở vòng thứ hai của nó.

Answer 2

Cho phép trình vòng lặp A và B xem danh sách tương ứng theo thứ tự và theo cặp. Consdier tồn tại một vòng lặp. Sau đó, tại thời điểm khi A đi vào vòng lặp, B sẽ ở một nơi nào đó bên trong vòng lặp đó. Nếu chiều dài của vòng lặp là K, sau đó B sẽ chạy xung quanh nó trong ]K/2[ di chuyển, vì vậy ở hầu hết trong 2*]K/2[ lặp chúng ta sẽ có được một tình huống khi B xuất hiện phía sau A trong một khoảng cách 1: B->A hoặc 2: B->.->A, và nó B 'lần lượt thứ. Sau này, rõ ràng, họ sẽ gặp nhau trong các động thái 1 hoặc 2. Vì vậy, nếu vòng lặp tồn tại và bắt đầu ở một số vị trí P, thì chúng tôi thực hiện tối đa 2*P + 2*]K/2[ + 2 = O(N) lần lặp.

Answer 3

//if you just want to check if there is a loop 

loop = false; 
item = head-of-list; 
while (item != nil) 
{ 
    if (item.next < 0) 
    { 
     loop = true; 
     break; 
    } 
    else 
    { 
     actual = item; 
     item = item.next; 
     actual.next = actual.next * -1; 
    } 
} 

return loop;