Đảo ngược LinkedList với Nodes có một con trỏ ngẫu nhiên

Question

Gần đây tôi đã xem qua câu hỏi thú vị này:

"Hãy xem xét một danh sách liên kết với mỗi Node, ngoài việc có một con trỏ 'bên cạnh' cũng có một con trỏ 'ngẫu nhiên'. Con trỏ 'ngẫu nhiên' trỏ đến một số Node ngẫu nhiên khác trong danh sách liên kết, nó cũng có thể trỏ tới NULL.

Bây giờ chúng ta được yêu cầu đảo ngược hướng của tất cả các con trỏ (cả 'tiếp theo' và 'ngẫu nhiên') của danh sách Liên kết. Ràng buộc là giải pháp PHẢI là O (1) độ phức tạp của không gian (Một hằng số số lượng các nút mới có thể là cr đã ăn nhưng không tỷ lệ với độ dài của danh sách) "

Tôi đã dành khá nhiều thời gian để suy nghĩ về điều này. Im không thực sự thuyết phục nó thực sự là có thể.

Answer 1

Điều đó là rất có thể. Tôi đã đưa ra một giải pháp có khả năng không tối ưu nhưng cho thấy rằng nó có thể được thực hiện. Đầu tiên chia nó thành hai vấn đề: đảo ngược các con trỏ tiếp theo và đảo ngược các con trỏ ngẫu nhiên.

Đảo ngược các con trỏ tiếp theo:

node* last = NULL; 
node* current = head; 
node* next = head->next; 
while (current != NULL) 
{ 
    current->next = last; 
    last = current; 
    current = next; 
    if (current != NULL) 
    next = current->next; 
} 
head = last 

Đảo ngược danh sách ngẫu nhiên là một chút phức tạp hơn, chỉ vì chúng ta không có một danh sách của tất cả những người đứng đầu của chuỗi con trỏ ngẫu nhiên, nhưng chúng ta có thể tìm ra tận cùng chúng (các nút sẽ là một con trỏ ngẫu nhiên NULL). Chúng tôi sẽ cần một số chức năng trợ giúp để làm điều đó. Đầu tiên là một để đảo ngược một danh sách ngẫu nhiên. Chúng tôi phần lớn sao chép mã từ phía trên. Lưu ý rằng chúng ta đang thiết lập kết thúc chuỗi là một giá trị đặc biệt. Điều này khiến chúng tôi không thể hoàn nguyên danh sách. Xem thảo luận trong phần bình luận để được giải thích.

node* chainTail = malloc(1); //mallocing here to get a unique pointer 
void reverseRandom(node* rhead) 
{ 
    node* last = chainTail; 
    node* current = rhead; 
    node* next = rhead->random; 
    while (current != NULL) 
    { 
    current->random = last; 
    last = current; 
    current = next; 
    if (current != NULL) 
     next = current->random; 
    } 
} 

Chúng tôi cũng cần một hàm trợ giúp để tìm cha mẹ của nút (hoặc trả về NULL nếu không có). Chúng tôi sẽ thực hiện tìm kiếm tuyến tính câm:

node* findParent(node* target) 
{ 
    node* candidate = head; 
    while ((candidate != NULL) && (candidate->random != target)) 
    candidate = candidate->next; 
    return candidate; 
} 

Bây giờ chúng ta chỉ cần đi bộ danh sách, tìm thấy bất kỳ nút mà có một giá trị ngẫu nhiên của NULL (đuôi chuỗi của chúng tôi), tìm người đứng đầu chuỗi của họ, và đảo ngược chuỗi:

node* current = head; //Current node in a linear walk looking for chain tails 
while (current != NULL) 
{ 
    if (NULL == current->random) 
    { 
    //current is the tail of a random chain, lets find the head 
    node* curr = current; //Current node in the search for the chain hean 
    node* parent = findParent(curr); 
    while (parent != NULL) 
    { 
     curr = parent; 
     parent = findParent(curr); 
    } 
    //At this point, curr is the head of the random chain, so reverse it 
    reverseRandom(curr); 
    } 
    current = current->next; 
} 

//Clean up chainTail pointers 
node* current; 
for (current = head; current != NULL; current = current->next) 
{ 
    if (current->random == chainTail) 
    { 
    current->random = NULL; 
    } 
} 
free(chainTail); //Stop a memory leak if this is not a global 

Tuyên bố từ chối trách nhiệm chuẩn: Tôi chưa chạy mã này. Nó có thể có lỗi. Tôi bắt đầu buồn ngủ gần cuối, vì vậy tôi có thể đã có một lỗi hợp lý, nhưng có vẻ như tôi làm việc.

Ngoài ra, nếu bạn đang tìm cách để đưa điều này vào sản xuất, thì không. Mã này chạy ở đâu đó xung quanh O (n^3). Điều này rất có thể không phải là giải pháp nhanh nhất. Nó sử dụng không gian liên tục (mặc dù thậm chí có thể được giảm bằng cách chia sẻ trong lớp lót và tích cực).

Answer 2

(Mở rộng về câu trả lời Konstantin N. của)

Để chắc chắn rằng bạn đang không lại đảo ngược bất cứ điều gì, bạn có thể bước qua danh sách, một nút cùng một lúc, từ trái sang phải, và lưu trữ chỉ mục của nút được kiểm tra cuối cùng.

lastIndex <- 0 
cur <- head 

while cur.next not null: 
    if cur.random is null: 
     randomHead <- # use Konstantin N's findParent helper 
     if get_index(randomHead) < lastIndex: 
      # we've already examined it 
     else: 
      # Konstantin N's reverseRandom() 
    cur <- cur.next 
    lastIndex <- lastIndex + 1 

// helper to find node index 
get_index(node): 
    cur <- head 
    ret <- 0 

    while cur.next not null: 
     if cur == node: 
      ret <- ret + 1 
    return ret 

Answer 3

Bạn cũng cần tính đến trường hợp chuỗi ngẫu nhiên tạo thành chu trình (đơn giản). Bạn có thể phát hiện chu trình bằng cách truyền tuyến tính của chuỗi; một lần nữa đảo ngược sẽ phải được xử lý nếu có một số chẵn các nút trong chu kỳ.

Answer 4

Dưới đây là nỗ lực của tôi tại giải pháp không gian giải pháp O (1) với độ phức tạp thời gian O (n).

static Node<E> reverseList(Node<E> head) { 
    if(head == null || head.next == null) { 
    return head; 
    } 

    Node<Integer> current = head; 
    Node temp = null; 

    // Reverse an existing Linked list. 
    while(current != null) { 
    Node previousNext = current.next; 
    current.next = temp; 
    temp = current; 
    current = previousNext; 
    } 

    reversedHead = temp; 
    while(temp != null) { 
    if(temp.jump != null) { 
     Node jumpTemp = temp.jump; 
     jumpTemp.jump = temp; 
     temp.jump = null; 
    } 
    temp = temp.next; 
    } 

    return reversedHead; 
}