Xóa bất kỳ nút nào khỏi một danh sách liên kết duy nhất khi chỉ con trỏ đến nút đó được đưa ra

Question

Đây là câu hỏi đặt ra cho tôi trong một cuộc phỏng vấn.

"Một danh sách liên kết duy nhất có trong bộ nhớ. Bạn phải xóa nút. Bạn cần viết hàm để xóa nút đó, chỉ mất địa chỉ của nút bị xóa làm đầu vào và không có gì khác (bao gồm cả đầu) "

Tôi đã đưa ra câu trả lời tương tự như câu trả lời trong bài đăng dưới đây - Sao chép nội dung của nút tiếp theo vào nút sẽ bị xóa và xóa nút tiếp theo.

Deleting a middle node from a single linked list when pointer to the previous node is not available

Nhưng người phỏng vấn hỏi tôi một lần nữa, những gì nếu tôi vượt qua địa chỉ của nút cuối cùng. Tôi đã nói với anh ta, vì tiếp theo sẽ là NULL, sao chép NULL vào trường dữ liệu cùng với địa chỉ đến nút tiếp theo cũng là NULL. Sau đó, ông nói với tôi sẽ có một vấn đề của con trỏ lủng lẳng ... mà tôi không hiểu một chút. Một số người có thể ném ánh sáng vào vấn đề này không? Có một giải pháp chung cho điều này?

Cập nhật (Hai ngày sau): Một chút bổ sung. Xem xét không có nút đặc biệt ở cuối danh sách. Và nút cuối cùng trỏ đến NULL và nếu nút đó được đưa ra làm đầu vào, làm thế nào để làm cho trước điểm nút cuối cùng thành NULL. Hay là không thể?

một cách đơn giản: Nếu một nút được cho là đầu vào cho một hàm, làm thế nào để làm cho con trỏ tham chiếu đến nó, trỏ đến NULL

Answer 1

Dangling con trỏ:

(http://en.wikipedia.org/wiki/Dangling_reference)

con trỏ Dangling và con trỏ hoang dã trong lập trình máy tính là con trỏ không trỏ đến một giá trị đối tượng của loại thích hợp. Đây là những trường hợp đặc biệt về vi phạm an toàn bộ nhớ.

Con trỏ lơ lửng phát sinh khi một đối tượng bị xóa hoặc bị phân phối, mà không sửa đổi giá trị của con trỏ, sao cho con trỏ vẫn còn điểm đến vị trí bộ nhớ của bộ nhớ được phân phối lại. Khi hệ thống có thể phân bổ lại bộ nhớ đã giải phóng trước đó cho một quá trình khác, nếu chương trình gốc sau đó dereferences con trỏ lơ lửng (hiện tại), hành vi không thể đoán trước có thể xảy ra, vì bộ nhớ hiện có thể chứa dữ liệu hoàn toàn khác.

Trong câu trả lời của bạn, để xóa nút đã cho, bạn thực sự xóa nút tiếp theo, có thể được tham chiếu bởi con trỏ. Đó là cách vấn đề con trỏ lơ lửng phát sinh.

(1) Không có tham chiếu bên ngoài nào trong danh sách, khi bạn làm rõ trong ghi chú. (2) Vấn đề con trỏ lơ lửng có thể phát sinh, như người phỏng vấn nói.

Cả hai (1) và (2) không thể chính xác cùng một lúc. Có nghĩa là có một sự hiểu lầm ở đâu đó.

Về Xóa Node cuối:

Nhưng người phỏng vấn hỏi tôi một lần nữa, những gì nếu tôi vượt qua địa chỉ của nút cuối cùng . Tôi đã nói với anh ta, vì tiếp theo sẽ là NULL, sao chép NULL vào trường dữ liệu cùng với địa chỉ đến nút tiếp theo là cũng NULL.

Tôi nghĩ bạn đang bối rối hai điều sau: (1) Một con trỏ p trỏ tới NULL, (2) Nút danh sách được liên kết có NULL trong trường dữ liệu của nó.

Giả sử cấu trúc dữ liệu là a -> b -> c -> d. Viết trường dữ liệu NULL thành d sẽ không làm cho phép c có con trỏ NULL trong trường next của nó.

Bạn có thể xóa nút cuối nếu danh sách được liên kết luôn có nút cuối cùng đặc biệt sẽ không bao giờ bị xóa. Ví dụ: a -> b -> c -> d -> LAST trong đó LAST có giá trị đặc biệt trong trường dữ liệu biểu thị nó thực sự là phần tử cuối cùng. Bây giờ để xóa d, bạn có thể xóa LAST và viết giá trị đặc biệt trong trường dữ liệu của d.

Có thể đây chính xác là những gì bạn đã cố gắng kể trong khi phỏng vấn, trong trường hợp đó phải có sự hiểu lầm giữa bạn và người phỏng vấn.

Answer 2

Nếu có các yếu tố khác đang trỏ đến nút tiếp theo đó sẽ được sao chép đến nút hiện tại và sau đó bị xóa, sau đó hoạt động này sẽ giới thiệu một lỗi. Vì vậy, trong câu trả lời của bạn, bạn nên nhấn mạnh rằng giải pháp của bạn chỉ hoạt động nếu không có tham chiếu bên ngoài vào danh sách.

Giải pháp của bạn chỉ hoạt động với nút cuối cùng nếu cấu trúc dữ liệu được tăng cường với phần tử "nút cuối cùng" cụ thể. (Nếu bạn đang sử dụng Smalltalk, bạn có thể viết self become: nil Không có ngôn ngữ nào khác có bất kỳ điều gì tương tự)

Không, không có giải pháp chung nếu có tham chiếu bên ngoài vào danh sách. Tôi nghĩ người phỏng vấn muốn xem liệu bạn có thực sự hiểu biết về chủ đề hay chỉ là lặp lại một câu trả lời được ghi nhớ.

Answer 3

bước:

1. Sao chép dữ liệu từ Node (i + 1) Node (i)
2. Sao chép NEXT của Node thứ hai (i + 1) vào một biến tạm thời.
3. Bây giờ xóa nút thứ hai (i + 1) // nó không yêu cầu con trỏ đến nút trước đó.

Chức năng:

void delete_node(node* node) 
{ 
    node->Data = node->Next->Data; 
    node* temp = node->Next->Next; 
    delete(node->Next); 
    node->Next = temp; 
} 

Answer 4

Có lẽ liên kết danh sách traversing của bạn có thể cần phải giả định rằng bất kỳ nút trỏ đến null là null nút không phụ thuộc vào giá trị ...

a->b->c->d->NULL 

nên d là nút null và nút không được coi là nút. theo cách này, bạn có thể tiết kiệm bằng cách sử dụng các giá trị đặc biệt vì chúng không đúng theo nghĩa chung. khác hơn là bạn sẽ không có bất kỳ cách nào khác cho nút trước đó để trỏ đến null.

Answer 5

thì sẽ có chương trình kiểm tra xem liệu nút cụ thể có phải là nút cuối cùng hay không.

void delete_node(node* node1) 
{ 
    node* search=head; 
    if(node1==head) 
    { 
     head=head->next; 
     search->next=NULL; 
     node1->next=NULL; 
    } 
    while(search->next != node1) 
     search=search->next; 
    if(node1->next==NULL) 
    { 
     search->next=NULL; 
    } 
    else 
    { 
     search->next=node1->next; 
     node1->next=NULL; 
    } 
    delete node1; 
} 

Answer 6

public void removeNode(Node node){ 

     /* if no node return null */ 
     if(node==null) return; 

     /* if only 1 node then delete node */ 
     if(node.getNext()==null) { 
      node = null; 
      return ; 
     } 

     /* copy next node data to this node */ 
     node.data = node.getNext().data(); 

     /* store the next next node */ 
     Node second = node.getNext().getNext(); 

     /* remove next node */ 
     removeNode(node.getNext()); 

     /* set the copied node as next */ 
     node.setNext(second); 
    } 

Answer 7

void deleteNode(Node * ptr) 
{ 
    Node *temp = ptr; 
    ptr = ptr->next; 
    temp->data = ptr->data; 
    temp->next = ptr->next; 
    free(ptr); 
} 

chúng tôi không thể đến Traverse Độc danh sách liên kết theo hướng ngược. Xóa nút có nghĩa là giải phóng bộ nhớ đó. Do đó, chỉ cần sao chép nội dung nút tiếp theo đến Cho con trỏ (địa chỉ bộ nhớ) và giải phóng nút tiếp theo. Nó sẽ giải quyết vấn đề của bạn .. Cảm ơn bạn ..