将当前节点设置为空?

goqiplq2  于 2021-07-09  发布在  Java
关注(0)|答案(4)|浏览(291)

我一直在练习破解编码面试中遇到的问题,我想出了一个解决方案,解决了一个要求删除链接列表中的中间节点的问题。

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 ?

qmb5sa22

qmb5sa221#

你的名单是双重链接的吗?那样的话,你可以

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

让垃圾收集发挥它的魔力。
在任何情况下,要回答您的问题,请了解对象的变量(例如 Node )在java中总是引用(指针)。
在你的工作中, current 是指向节点对象的变量。如果你把它设成 null ,它没有指向任何地方。但这并没有改变列表的结构。

sy5wg1nm

sy5wg1nm2#

如果是双链表,我们只需要将mid.pre链接到mid.next,如果是单链表,我们需要从开始遍历到中间(我们需要上一个节点) Prv.next = mid )换个地方就行了 prv.next = mid.next .
问题:在你们两种解决方案中,移除中间节点后如何从头部遍历?

1wnzp6jl

1wnzp6jl3#

我不明白为什么它不首先给出以下代码的编译错误:

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;
}
mfpqipee

mfpqipee4#

回答你的问题,因为这是一个死代码的例子。它是一个局部变量,因此,由于对它的最终写入不会被任何代码读取,因此对程序没有任何影响。
即:

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` 不需要为任何链表操作重新分配。

相关问题