Установка текущего узла на нуль?

Question

Я практиковал проблемы с Cracking the Coding Interview, и я придумал решение проблемы с просьбой удалить средний узел в связанном списке.

public void deleteMidNode(Node mid){ 
    if(mid == head || mid.next==null){ 
     return; 
    } 
    Node current = mid; 
    while(current.next.next!=null){ 
     current.data = current.next.data; 
     current = current.next; 
    } 
    current.next = null; 
} 

Теперь этот код действительно работает - я его протестировал. Тем не менее, мне очень интересно, почему я могу установить current.next обнулить, но если бы я должен был сделать это он не работает:

public void deleteMidNode(Node mid){ 
    if(mid == head || mid.next==null){ 
     return; 
    } 

    Node current = mid; 
    while(current.next!=null){ 
     current.data = current.next.data; 
     current = current.next; 
    } 
    current = null;  
} 

Может кто-нибудь сказать мне, почему я не могу установить текущий узел в null?

Answer 1

Чтобы ответить на ваш вопрос, потому что это пример мертвого кода. Это локальная переменная, так как окончательная запись на нее не считывается никаким кодом, она не будет влиять на программу.

То есть:

current = null; 
    //there are no reads of "current" here before: 
} //the end of method which is the end of scope for the local "current" 

Порядочный IDE будет намекнуть вам, что эта запись не была прочитана, с помощью, например, серый цветом, подчеркивание или иначе выделяя мертвый код.

Я не думаю, что стоит слишком тщательно анализировать ваш код, хотя это совершенно неправильно. Я боюсь, что удаление элемента из связанного списка должно быть процедурой постоянного времени O (1) (по крайней мере, узел и предыдущий узел). Вы перемещаете данные вокруг, вызывая его O (n), что означает, что он не эффективнее, чем удаление из массива данных.

Учитывая это:

node1 -> node2 -> node3 -> node4 
    |  |  |  | 
data1 data2 data3 data4 

node2 Удаление, следует перейти к:

node1 -> node3 -> node4 
    |  |  | 
data1 data3 data4 

Но вы перемещаете данные вокруг, как будто перетасовки элементы вместе в массиве. Это приводит к тому, что это будет:

node1 -> node2 -> node3 
    |  |  | 
data1 data3 data4 

current.data никогда не должен быть переназначен для любых связанных операций списка.

Answer 2

Является ли ваш список двусвязным? В этом случае вы можете просто сделать

if (mid != null) { 
    mid.prev.next = mid.next 
    mid.next.prev = mid.prev 
} 

и пусть сбор мусора совершит свою магию.

В любом случае, чтобы ответить на ваш вопрос, поймите, что переменные для объектов (например, Node) в Java всегда являются ссылками (указателями).

В вашей функции current - это переменная, указывающая на объект узла. Если вы установите его на null, он нигде не укажет. Но это не меняет структуру списка.

Answer 3

Если это двойной список, нам нужно просто связать mid.pre с mid.next, если это singleLinked List, нам нужно пройтись от начала до середины (нам нужен предыдущий узел Prv.next = mid) и просто замените prv.next = mid.next.

Вопрос: В обоих ваших решениях, как мы можем перемещаться из головы после удаления среднего узла?

Answer 4

Я не понимаю, почему это в первую очередь не дает ошибку компиляции для кода ниже:

current = current.next; 

Это должно дать ошибку компиляции, так как вы присваиваете указатель узла к узлу.

Когда я запускаю ту же функцию при прохождении указателя, она работает.

#include<stdio.h> 
#include<malloc.h> // C library to handle malloc functions 

struct node{ // struct node declaration 
    int data; 
    struct node* link; 
}; 
void deleteNode(struct node*); 
void printList(struct node*); 
int main(){ 
    struct node* head; 
    struct node* first; 
    struct node* second; 
    struct node* third; 
    struct node* fourth; 
    struct node* fifth; 
    struct node* sixth; 
    head = (struct node*)malloc(sizeof(struct node)); 
    first = (struct node*)malloc(sizeof(struct node)); 
    second = (struct node*)malloc(sizeof(struct node)); 
    third = (struct node*)malloc(sizeof(struct node)); 
    fourth = (struct node*)malloc(sizeof(struct node)); 
    fifth = (struct node*)malloc(sizeof(struct node)); 
    sixth = (struct node*)malloc(sizeof(struct node)); 
    head->link = first; 
    first->link = second; 
    second->link = third; 
    third->link = fourth; 
    fourth->link = fifth; 
    fifth->link = sixth; 
    sixth->link = NULL; 
    head-> data = 1; 
    first-> data = 2; 
    second-> data = 3; 
    third-> data = 4; 
    fourth-> data = 5; 
    fifth-> data = 6; 
    sixth-> data = 7; 
    printList(head); 
    deleteNode(second); 
    printList(head); 
} 
void printList(struct node* head){ 
    struct node* node = head; 
    while(node->link!= NULL){ 
     printf("%d\n",node->data); 
     node= node->link; 
    } 
} 
void deleteNode(struct node* kid){ 
    struct node* mid = kid; 
    while(mid->link!= NULL){ 
     mid->data = mid->link->data; 
     mid = mid->link; 
    } 
    mid = NULL; 
}