Tìm chu trình trong danh sách liên kết

#1

Mình cần sự trợ giúp và những ý kiến thảo luận của các bạn về bài toán sau:

Đề bài:
Hình minh họa:

blob.jpg771×142 17.8 KB

Cho một danh sách liên kết đơn một chiều. Chu trình trong danh sách là khi duyệt từ head tới một node rồi từ node đó duyệt tiếp thì sẽ quay trở lại một node đã duyệt trước đó. (Mình suy ra là không có con trỏ tail và điểm dừng khi thực hiện phép duyệt).
Yêu cầu xác định trong một danh sách có chu trình hay không với thời gian O(n) và giới hạn bộ nhớ là O(1) {gồm head và một số biến không quá một số C cho trước}.
p/s: n này không cho trước,

#2

Không rõ bài này là duyệt một node bất kỳ thì sẽ có thể duyệt được node trước đó (trừ head node), hay chỉ có tail node mới duyệt được node trước đó ?

Vì để node bất kỳ node nào cũng có thể duyệt lại node trước đó thì phải là double-queue, thì sẽ không thoả mãn điều kiện liên kết đơn một chiều.

#3

Có phải y bạn là thế này, cho 1 danh sách 1 chiều. 1->2->3->null thì khi p=3; khi p->next=null thì p->next =2. vậy thì tức là ta duyệt tới null xong cho danh sách quay ngược về bằng cách tìm p đứng trước nó không, thực ra p->next không chỉ chỏ đến 2 mà có thể đến bất kì chỗ nào, để chở thành 1 chu trình như bạn muốn.

#4

Đúng rồi các bạn nhé chu trình thì có thể trỏ tới bất kỳ node nào trước đó. (tức node đã duyệt qua từ head):
Mình ví dụ nhé:
a> danh sách đầu từ 1->2->3->null => không có chu trình.
b> danh sách thứ 2 từ 1->2->3->2 => có chu trình.
Nhưng vấn đề ở đây là “Xác định trong danh sách đã cho sẵn Có hay Không chu trình”?
Nhưng mình chưa biết giải thuật thế nào!

#5

Chỉ một thôi bạn --> INPUT: một danh sách liên kết -->Giải thuật: cách xác định có hay không chu trình --> OUTPUT: có hay không có.

#6

Thuật toán:
gán node đầu tiên cho 2 biến: jump1 và jump2.
cho duyệt dslk từ đầu đến cuối list bằng cách sau:

  • biến jump1 sẽ nhảy đến 1 node kế tiếp.
  • biến jump2 sẽ nhảy 1 lần 2 node kế tiếp.
    Sau 1 số lần duyệt nhất định. Nếu jump1 == jump2 => có tồn tại chu trình. Nếu jump2 chạm tới Null thì không có chu trình.

Chứng minh: phần này hơi rắc rối nên không post, bạn tự chứng minh xem sao.

3 Likes
#7

Vâng cảm ơn bạn đã giúp. Nó đúng rồi. Mình sẽ cố nghĩ cách chứng minh.

#8

Đúng như bạn Quân nói nhưng mình có góp thêm ý kiến là bận nên chọn jump1 là cái Node cuối, cho jump 2 chạy từ đầu, nếu nó gặp nhau 2 lần thì chuẩn( vì nếu gán jump1 ko cẩn thận có thể chu trình lặp lại ko qua jump1 nữa).

#9

Bạn lưu ý hộ mình đây là dslk đơn 1 chiều, nên làm sao có thể biết node cuối ngay từ đầu được, ngoài ra 1 khi jump1 và jump2 đã nhảy vào trong cùng 1 vòng lặp node thì sau 1 số hữu hạn lần thì jump1 sẽ bằng jump2 không quan trọng điểm bắt đầu tại vị trí nào của jump1 và jump2 ở trong vòng lặp node đó

1 Like
#10

Xét 1 chu trình:
-Giả sử j1 đang ở ngay trước j2 (j1 trước j2 1 ô) => bước tiếp theo j1 trùng j2
-Giả sử j1 đang ở trước cách j2 1 ô (j1 trước j2 2 ô) => bước tiếp theo j1 cách j2 1 ô
-Giả sử j1 trước j2 k ô => cần k bước để j1 trùng j2

Nếu chu trình có m node thì k<<>m (k=m thì j1 trùng j2 rồi) => số j1 đếm trong chu trình nhỏ hơn kích thước chu trình. Mà số bước j1 đi trước khi vào chu trình đúng bằng số node ngoài chu trình nên độ phức tạp của thuật toán là O(n), max = n-1

Nếu n node liên kết không có chu trình, thuật toán kết thúc với số bước là n/2+1 (n/2+2 với n chẵn) vì j2 luôn đi nhanh hơn j1.

2 Likes
#11

max = n chứ, lỡ cả cái list là chu trình thì con rùa chạy đúng 1 vòng, con thỏ chạy đúng 2 vòng mới gặp lại nhau :joy:

#12

A đù, trường hợp duy nhất j1=j2 mà vẫn phải đếm :joy:

#14

à ừ, ý mình là nếu là ngưới code thì nếu có ý đồ viết code thì có thể biết đâu là phần tử cuối và theo như mình nói thì cho j1 là phần tử cuối đó. còn j1 có thể ở trong danh sách nhưng chưa chắc đã được duyệt đến trong các vòng lặp có phải không? VD: 1-2-3-2-3-2-3

#15
  1. Bạn phân tích hộ mình cái, đây là dslk đơn, do đó chu trình chỉ xảy ra ở node cuối cùng, tức là node cuối cùng hoặc là không trỏ tới đâu cả, hoặc là sẽ trỏ đến một node nào đó nằm trong dslk, các node còn lại luôn tuân thủ quy tắc của dslk, nghĩa là nếu bỏ đi node cuối thì sẽ luôn không có 1 chu trình. Do đó VD của bạn sẽ luôn không tồn tại. Jump1 sẽ luôn đi vào chu trình (nếu có).
  2. Cho dù bạn là tác giả của code cũng chưa chắc bạn biết được node cuối nếu không bắt caller truyền pointer node cuối vào cho bạn, mà như vậy thì rất confused, vì dslk có thể được tạo ra từ bất cứ đâu, và được bất cứ phần nào của chương trình gọi tới tại bất kì thời điểm nào, thông qua rất nhiều stack caller
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?