Thuật toán tốt nhất để kiểm tra xem danh sách được liên kết có chu kỳ

Question

Thuật toán (ngắt) tốt nhất để xác định xem danh sách được liên kết có chu trình trong đó không?

[Chỉnh sửa] Phân tích độ phức tạp tiệm cận cho cả thời gian và không gian sẽ trở nên ngọt ngào để các câu trả lời có thể được so sánh tốt hơn.

[Chỉnh sửa] Câu hỏi gốc không giải quyết các nút có mức độ vượt trội> 1, nhưng có một số người nói về nó. Câu hỏi đó là nhiều hơn dọc theo dòng của "thuật toán tốt nhất để phát hiện chu kỳ trong một đồ thị trực tiếp".

Answer 1

Có hai con trỏ lặp qua danh sách; làm cho một lần lặp lại với tốc độ gấp đôi tốc độ của cái kia và so sánh vị trí của chúng ở mỗi bước. Trên đầu của tôi, một cái gì đó như:

node* tortoise(begin), * hare(begin); 
while(hare = hare->next) 
{ 
    if(hare == tortoise) { throw std::logic_error("There's a cycle"); } 
    hare = hare->next; 
    if(hare == tortoise) { throw std::logic_error("There's a cycle"); } 
    tortoise = tortoise->next; 
} 

O (n), tốt như bạn có thể nhận được.

Answer 2

Điều gì về việc sử dụng bảng băm để lưu trữ các nút đã xem (bạn xem chúng theo thứ tự từ đầu danh sách)? Trong thực tế, bạn có thể đạt được một cái gì đó gần với O (N).

Nếu không, sử dụng một vùng được sắp xếp thay vì bảng băm sẽ đạt được O (N log (N)).

Answer 3

Tôi tự hỏi nếu có bất kỳ cách nào khác hơn là chỉ đi lặp đi lặp lại - cư một mảng khi bạn bước về phía trước, và kiểm tra xem nút hiện hành đã có mặt trong mảng ...

Answer 4

thuật toán Konrad Rudolph sẽ không hoạt động nếu chu kỳ không trỏ đến điểm bắt đầu. Danh sách sau đây sẽ làm cho nó trở thành một vòng lặp vô hạn: 1-> 2-> 3-> 2.

Thuật toán của DrPizza chắc chắn là cách để thực hiện.

Answer 5

Trong trường hợp này đang OysterD sẽ là giải pháp nhanh nhất (đỉnh màu)

Đó sẽ thực sự làm tôi ngạc nhiên. Giải pháp của tôi làm cho tối đa hai lượt đi qua danh sách (nếu nút cuối cùng được liên kết với nút áp chót), và trong trường hợp thông thường (không có vòng lặp) sẽ chỉ thực hiện một lần. Với không băm, không phân bổ bộ nhớ, vv

Answer 6

Trong trường hợp này đang OysterD sẽ là giải pháp nhanh nhất (đỉnh màu)

Đó sẽ thực sự làm tôi ngạc nhiên. Giải pháp của tôi làm cho tối đa hai lượt đi qua danh sách (nếu nút cuối cùng được liên kết với nút áp chót), và trong trường hợp thông thường (không có vòng lặp) sẽ chỉ thực hiện một lần. Không băm, không phân bổ bộ nhớ, v.v.

Có. Tôi đã nhận thấy rằng công thức không hoàn hảo và đã lặp lại nó. Tôi vẫn tin rằng một băm thông minh có thể hoạt động nhanh hơn - bằng tóc. Tôi tin rằng thuật toán của bạn là là là giải pháp tốt nhất.

Chỉ cần nhấn mạnh điểm của tôi: màu vertec được sử dụng để phát hiện các chu kỳ phụ thuộc bởi bộ thu gom rác hiện đại để có trường hợp sử dụng rất thực tế cho nó. Họ chủ yếu sử dụng cờ bit để thực hiện màu.

Answer 7

Bạn sẽ phải truy cập mọi nút để xác định điều này. Điều này có thể được thực hiện đệ quy.Để ngăn bạn truy cập các nút đã truy cập, bạn cần một lá cờ để nói 'đã được truy cập'. Điều này tất nhiên không cung cấp cho bạn vòng. Vì vậy, thay vì một lá cờ bit, hãy sử dụng một số. Bắt đầu lúc 1. Kiểm tra các nút đã kết nối và sau đó đánh dấu các nút này là 2 và chọn lại cho đến khi mạng được bao phủ. Nếu khi kiểm tra các nút bạn gặp phải một nút nhỏ hơn một nút, thì bạn có một chu kỳ. Độ dài chu kỳ được đưa ra bởi sự khác biệt.

Answer 8

Điều kiện tiên quyết: Theo dõi kích thước danh sách (cập nhật kích thước khi một nút được thêm hoặc xóa).

phát hiện Loop:

1. Giữ một bộ đếm khi vượt qua kích thước danh sách.

2. Nếu bộ đếm vượt quá kích thước danh sách, có thể có chu kỳ.

phức tạp: O (n)

Lưu ý: so sánh giữa quầy và kích thước danh sách, cũng như các hoạt động cập nhật của kích thước danh sách, phải được thực hiện thread-safe.

Answer 9

Hai con trỏ được khởi tạo ở đầu danh sách. Một con trỏ chuyển tiếp một lần ở mỗi bước, và con trỏ chuyển tiếp hai lần ở mỗi bước. Nếu con trỏ nhanh hơn đáp ứng chậm hơn một lần nữa, có một vòng lặp trong danh sách. Nếu không, sẽ không có vòng lặp nếu kết nối nhanh hơn đến cuối danh sách.

Mã mẫu bên dưới được triển khai theo giải pháp này. Con trỏ nhanh hơn là pFast, và con trỏ chậm hơn là pSlow.

bool HasLoop(ListNode* pHead) 
{ 
    if(pHead == NULL) 
     return false; 


    ListNode* pSlow = pHead->m_pNext; 
    if(pSlow == NULL) 
     return false; 


    ListNode* pFast = pSlow->m_pNext; 
    while(pFast != NULL && pSlow != NULL) 
    { 
     if(pFast == pSlow) 
      return true; 


     pSlow = pSlow->m_pNext; 


     pFast = pFast->m_pNext; 
     if(pFast != NULL) 
      pFast = pFast->m_pNext; 
    } 


    return false; 
} 

Giải pháp này có sẵn trên my blog. Có một vấn đề khác được thảo luận trong blog: Nút nhập là gì khi có chu kỳ/vòng lặp trong một danh sách?

Answer 10

"Hack" giải pháp (nên làm việc trong C/C++):

• Traverse danh sách, và thiết lập các bit cuối cùng của next con trỏ đến 1.
• Nếu tìm yếu tố có con trỏ gắn cờ - trả về true và phần tử đầu tiên của chu kỳ.
• Trước khi trở về, hãy đặt lại con trỏ, mặc dù tôi tin rằng dereferencing sẽ hoạt động ngay cả với con trỏ được gắn cờ.

Độ phức tạp của thời gian là 2n. Có vẻ như nó không sử dụng bất kỳ biến thời gian nào.

Answer 11

Take 2 con trỏ * p và q *, bắt đầu đi qua danh sách liên kết "LL" sử dụng cả hai con trỏ:

1) con trỏ p sẽ xóa nút trước mỗi lần và trỏ đến nút tiếp theo.

2) con trỏ q sẽ đi mỗi lần theo hướng chỉ về phía trước.

điều kiện:

1) con trỏ p trỏ null và q được trỏ đến một số nút: Vòng hiện diện

2) cả hai con trỏ trỏ đến null: không có vòng lặp là có

Answer 12

này là một giải pháp sử dụng một bảng Hash (chỉ là một danh sách thực sự) để lưu địa chỉ con trỏ.

def hash_cycle(node): 
    hashl=[] 
    while(node): 
     if node in hashl: 
      return True 
     else: 
      hashl.append(node) 
      node=node.next 
    return False