将当前节点设置为空?

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

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

  1. public void deleteMidNode(Node mid){
  2. if(mid == head || mid.next==null){
  3. return;
  4. }
  5. Node current = mid;
  6. while(current.next.next!=null){
  7. current.data = current.next.data;
  8. current = current.next;
  9. }
  10. current.next = null;
  11. }

现在这个代码可以工作了-我已经测试过了。但是,我很好奇为什么我可以 current.next 为空,但如果我要这样做,它不起作用:

  1. public void deleteMidNode(Node mid){
  2. if(mid == head || mid.next==null){
  3. return;
  4. }
  5. Node current = mid;
  6. while(current.next!=null){
  7. current.data = current.next.data;
  8. current = current.next;
  9. }
  10. current = null;
  11. }

有人能告诉我为什么不能将当前节点设置为 null ?

qmb5sa22

qmb5sa221#

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

  1. if (mid != null) {
  2. mid.prev.next = mid.next
  3. mid.next.prev = mid.prev
  4. }

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

sy5wg1nm

sy5wg1nm2#

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

1wnzp6jl

1wnzp6jl3#

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

  1. current = current.next;

这将导致编译错误,因为您正在将节点指针分配给节点。
当我在传递指针的同时运行相同的函数时,它就工作了。

  1. # include<stdio.h>
  2. # include<malloc.h> // C library to handle malloc functions
  3. struct node{ // struct node declaration
  4. int data;
  5. struct node* link;
  6. };
  7. void deleteNode(struct node*);
  8. void printList(struct node*);
  9. int main(){
  10. struct node* head;
  11. struct node* first;
  12. struct node* second;
  13. struct node* third;
  14. struct node* fourth;
  15. struct node* fifth;
  16. struct node* sixth;
  17. head = (struct node*)malloc(sizeof(struct node));
  18. first = (struct node*)malloc(sizeof(struct node));
  19. second = (struct node*)malloc(sizeof(struct node));
  20. third = (struct node*)malloc(sizeof(struct node));
  21. fourth = (struct node*)malloc(sizeof(struct node));
  22. fifth = (struct node*)malloc(sizeof(struct node));
  23. sixth = (struct node*)malloc(sizeof(struct node));
  24. head->link = first;
  25. first->link = second;
  26. second->link = third;
  27. third->link = fourth;
  28. fourth->link = fifth;
  29. fifth->link = sixth;
  30. sixth->link = NULL;
  31. head-> data = 1;
  32. first-> data = 2;
  33. second-> data = 3;
  34. third-> data = 4;
  35. fourth-> data = 5;
  36. fifth-> data = 6;
  37. sixth-> data = 7;
  38. printList(head);
  39. deleteNode(second);
  40. printList(head);
  41. }
  42. void printList(struct node* head){
  43. struct node* node = head;
  44. while(node->link!= NULL){
  45. printf("%d\n",node->data);
  46. node= node->link;
  47. }
  48. }
  49. void deleteNode(struct node* kid){
  50. struct node* mid = kid;
  51. while(mid->link!= NULL){
  52. mid->data = mid->link->data;
  53. mid = mid->link;
  54. }
  55. mid = NULL;
  56. }
展开查看全部
mfpqipee

mfpqipee4#

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

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

一个像样的ide会向您暗示,这篇文章不是通过灰显、下划线或以其他方式突出显示死代码来读取的。
我认为不值得过于仔细地分析您的代码,尽管这恐怕是完全错误的,从链表中删除项目应该是一个o(1)常量时间过程(至少在找到节点和上一个节点之后)。您将数据四处移动,使其成为o(n),这意味着它的效率并不比从数据数组中删除更高。
鉴于此:

  1. node1 -> node2 -> node3 -> node4
  2. | | | |
  3. data1 data2 data3 data4

正在删除 node2 ,应转到:

  1. node1 -> node3 -> node4
  2. | | |
  3. data1 data3 data4

但是移动数据就像在数组中移动项目一样。这导致:

  1. node1 -> node2 -> node3
  2. | | |
  3. data1 data3 data4
  4. ``` `current.data` 不需要为任何链表操作重新分配。
展开查看全部

相关问题