題目:給定單向鏈表的頭指針和一個節點指針,定義一個函數在O(1)時間刪除該節點。

鏈表節點與函數的定義如下。

?

通常我們刪除某個節點都是從頭開始遍歷到需要刪除節點的前一個節點。

然后使得該節點的next指向刪除節點的next即可，這樣看來刪除一個節點

的復雜度為O(n)然而我們其實遍歷的目的只是想獲取想要刪除節點的前一

個節點。

?

?

那么我們可以這樣考慮:

我們把要刪除節點下一個節點的值賦值到當前節點，然后將當前節點的下一個

節點刪除即可。

?

比如:

一個鏈表3->2->5->7->9給定的指針指向5也就是說要刪除5這個節點。

我們將節點5下個節點的值賦值給需要刪除的節點即:

3->2->7->7->9

然后再p->next=p->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(node==NULL) 11 return; 12 13 struct ListNode* p,*q; 14 q=node; 15 p=node->next; 16 q->val=p->val; 17 q->next=p->next; 18 19 }

?

勘誤:

上面的方法沒有考慮到當要刪除的結點是尾結點的情況

因此當需要刪除的結點為尾結點的時候這時候仍需要

從頭遍歷到尾結點的前面一個結點。

但是算法復雜度仍然為1,因為只有一個尾結點需要遍歷

整個鏈表,復雜度為(O(n)+O(1)*(n-1))/n=O(1)

?

代碼實現如下:

1 #include <iostream> 2 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(node==NULL) 22 return; 23 if(node->next==NULL) 24 { 25 ListNode *TempHead; 26 TempHead=head; 27 while(TempHead->next->next!=NULL) 28 { 29 TempHead=TempHead->next; 30 } 31 TempHead->next=NULL; 32 return; 33 } 34 35 36 struct ListNode *p,*q; 37 q=node; 38 p=node->next; 39 q->val=p->val; 40 q->next=p->next; 41 } 42 43 44 ListNode* CreateList() 45 { 46 ListNode *Head,*p; 47 Head=(ListNode*)malloc(sizeof(ListNode)); 48 if(Head==NULL) 49 return NULL; 50 51 Head->val=0; 52 Head->next=NULL; 53 p=Head; 54 while(true) 55 { 56 int data; 57 cout<<"Please input Node data: "; 58 cin>>data; 59 if(data==0) 60 { 61 break; 62 } 63 else 64 { 65 ListNode* NewNode; 66 NewNode=(ListNode*)malloc(sizeof(ListNode)); 67 NewNode->val=data; 68 NewNode->next=NULL; 69 p->next=NewNode; 70 p=p->next; 71 } 72 } 73 74 75 return Head->next; 76 } 77 78 79 void PrintList(ListNode* Head) 80 { 81 ListNode *p; 82 p=Head; 83 84 while(p!=NULL) 85 { 86 cout<<p->val<<","; 87 p=p->next; 88 } 89 } 90 91 ListNode* GetNodePtr(ListNode* Head) 92 { 93 int count; 94 ListNode* p; 95 p=Head; 96 cout<<"Please input the Node Order you want to delete: "; 97 cin>>count; 98 int i=0; 99 while(i<count-1) 100 { 101 p=p->next; 102 i++; 103 } 104 105 return p; 106 } 107 108 109 int main() 110 { 111 ListNode *Node; 112 head=CreateList(); 113 cout<<"The list is: "; 114 PrintList(head); 115 cout<<endl; 116 Node=GetNodePtr(head); 117 deleteNode(Node); 118 cout<<"The delete node list is: "; 119 PrintList(head); 120 cout<<endl; 121 return 0; 122 }

測試結果如下:

?

感謝@rainhard指出這個錯誤

轉載于:https://www.cnblogs.com/vpoet/p/4671566.html

總結

以上是生活随笔為你收集整理的剑指offer-面试题13.在O(1)时间删除链表节点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。