中国国家住房和城乡建设部网站首页,利为汇网站建设,汉寿网站建设,创网站题目:给定单向链表的头指针和一个节点指针,定义一个函数在O(1)时间删除该节点。 链表节点与函数的定义如下。 通常我们删除某个节点都是从头开始遍历到需要删除节点的前一个节点。 然后使得该节点的next指向删除节点的next即可#xff0c;这样看来删除一个节点 的复杂度为O(n)…题目:给定单向链表的头指针和一个节点指针,定义一个函数在O(1)时间删除该节点。 链表节点与函数的定义如下。 通常我们删除某个节点都是从头开始遍历到需要删除节点的前一个节点。 然后使得该节点的next指向删除节点的next即可这样看来删除一个节点 的复杂度为O(n)然而我们其实遍历的目的只是想获取想要删除节点的前一 个节点。 那么我们可以这样考虑: 我们把要删除节点下一个节点的值赋值到当前节点然后将当前节点的下一个 节点删除即可。 比如: 一个链表3-2-5-7-9给定的指针指向5也就是说要删除5这个节点。 我们将节点5下个节点的值赋值给需要删除的节点即: 3-2-7-7-9 然后再p-nextp-next-next即可删除 代码实现如下: 1 /**2 * Definition for singly-linked list.3 * struct ListNode {4 * int val;5 * struct ListNode *next;6 * };7 */8 void deleteNode(struct ListNode* node) 9 {
10 if(nodeNULL)
11 return;
12
13 struct ListNode* p,*q;
14 qnode;
15 pnode-next;
16 q-valp-val;
17 q-nextp-next;
18
19 } 勘误: 上面的方法没有考虑到当要删除的结点是尾结点的情况 因此当需要删除的结点为尾结点的时候这时候仍需要 从头遍历到尾结点的前面一个结点。 但是算法复杂度仍然为1,因为只有一个尾结点需要遍历 整个链表,复杂度为(O(n)O(1)*(n-1))/nO(1) 代码实现如下: 1 #include iostream2 using namespace std;3 4 /**5 * Definition for singly-linked list.6 * struct ListNode {7 * int val;8 * struct ListNode *next;9 * };10 */11 struct ListNode 12 {13 int val;14 struct ListNode *next;15 };16 17 ListNode *head;18 19 void deleteNode(struct ListNode* node) 20 {21 if(nodeNULL)22 return;23 if(node-nextNULL)24 {25 ListNode *TempHead;26 TempHeadhead;27 while(TempHead-next-next!NULL)28 {29 TempHeadTempHead-next;30 }31 TempHead-nextNULL;32 return;33 }34 35 36 struct ListNode *p,*q;37 qnode;38 pnode-next;39 q-valp-val;40 q-nextp-next; 41 }42 43 44 ListNode* CreateList()45 {46 ListNode *Head,*p;47 Head(ListNode*)malloc(sizeof(ListNode));48 if(HeadNULL)49 return NULL;50 51 Head-val0;52 Head-nextNULL;53 pHead;54 while(true)55 {56 int data;57 coutPlease input Node data: ;58 cindata;59 if(data0)60 {61 break;62 }63 else64 {65 ListNode* NewNode;66 NewNode(ListNode*)malloc(sizeof(ListNode));67 NewNode-valdata;68 NewNode-nextNULL;69 p-nextNewNode;70 pp-next;71 }72 }73 74 75 return Head-next;76 }77 78 79 void PrintList(ListNode* Head)80 {81 ListNode *p;82 pHead;83 84 while(p!NULL)85 {86 coutp-val,;87 pp-next;88 }89 }90 91 ListNode* GetNodePtr(ListNode* Head)92 {93 int count;94 ListNode* p;95 pHead;96 coutPlease input the Node Order you want to delete: ;97 cincount;98 int i0;99 while(icount-1)
100 {
101 pp-next;
102 i;
103 }
104
105 return p;
106 }
107
108
109 int main()
110 {
111 ListNode *Node;
112 headCreateList();
113 coutThe list is: ;
114 PrintList(head);
115 coutendl;
116 NodeGetNodePtr(head);
117 deleteNode(Node);
118 coutThe delete node list is: ;
119 PrintList(head);
120 coutendl;
121 return 0;
122 } 测试结果如下: 感谢rainhard指出这个错误转载于:https://www.cnblogs.com/vpoet/p/4671566.html
