1.单向链表删除指定节点
-
常规思路:从头遍历到指定节点前一个节点Pre,然后将Pre的next指向指定节点的下一个,删除指定节点即可。O(n)
-
将指定节点下一个的内容复制到指定节点,然后删除其下一个节点。O(1)
2.代码
void deleteNode(ListNode **head, ListNode *toDelete)
{if(!head || !toDelete)return;if(toDelete->next != null)//非尾节点{ListNode* next = toDelete->next;toDelete->value = next->value;toDelete->next = next->next;delete next;next = NULL;}else if(*head == toDelete)//尾节点,但整个链表只有一个节点{delete toDelete;toDelete = NULL:*head = NULL;}else//尾节点,链表有多个节点{ListNode* node = *head;while(node->next != toDelete){node = node->next;}node-next = NULL;delete toDelete;toDelete = NULL;}
}
3.复杂度
-
仅当链表有多个节点,删除尾节点时,需要遍历,时间复杂度O(n)
-
非尾节点或者尾节点就是头节点,都是O(1)
-
平均复杂度还是O(1)
-
由于受到O(1)复杂度限制,代码不能检测toDelete是否在链表中,只能假设输入无误