今天做到一道题：设一个有序的单链表中有n个节点，现要求插入一个新节点后是的单链表仍保持有序，则该操作的时间为：。
答案是：O(n) 为什么？ 因为它是链表！ 链表的增删改功能，一定依托于其“low的一批”的“ 遍历 ”，这是链表的核心。插入一个数据，就要遍历一遍，有n个节点，时间复杂度就是O(n)。
为什么强调是“单链表”呢？ 因为在实际的软件开发中，从链表中删除一个数据无外乎这两种情况： 删除结点中“值等于某个给定值”的结点 删除给定指针指向的结点
针对第二种情况，单链表删除操作需要 O(n) 的时间复杂度，而双向链表只需要在 O(1) 的时间复杂度。
这一部分我自认为没有能力讲解清楚，相比自己，我更想为大家推荐一篇文章（@程序员小吴）：冰与火之歌：时间与空间复杂度
给定一个单链表中的表头和一个等待被删除的节点。请在 O(1) 时间复杂度删除该链表节点。并在删除该节点后，返回表头。
示例： 给定 1->2->3->4，和节点 3，返回 1->2->4。
在之前介绍的单链表删除节点中，最普通的方法就是遍历链表，复杂度为O(n)。 如果我们把删除节点的下一个结点的值赋值给要删除的结点，然后删除这个结点，这相当于删除了需要删除的那个结点。因为我们很容易获取到删除节点的下一个节点，所以复杂度只需要O(1)。
示例： 单链表：1->2->3->4->NULL 若要删除节点 3 。第一步将节点3的下一个节点的值4赋值给当前节点。变成 1->2->4->4->NULL，然后将就 4 这个结点删除，就达到目的了。 1->2->4->NULL 如果删除的节点的是头节点，把头结点指向 NULL。 如果删除的节点的是尾节点，那只能从头遍历到头节点的上一个结点。
代码展示：
void deleteNode(ListNode **pHead, ListNode* pDelNode) { if(pDelNode == NULL) return; if(pDelNode->next != NULL){ ListNode *pNext = pDelNode->next; //下一个节点值赋给待删除节点 pDelNode->val = pNext->val; //待删除节点指针指后面第二个节点 pDelNode->next = pNext->next; //删除待删除节点的下一个节点 delete pNext; pNext = NULL; }else if(*pHead == pDelNode)//删除的节点是头节点 { delete pDelNode; pDelNode= NULL; *pHead = NULL; } else//删除的是尾节点 { ListNode *pNode = *pHead; while(pNode->next != pDelNode) { pNode = pNode->next; } pNode->next = NULL; delete pDelNode; pDelNode= NULL; } } 行舟客 认证博客专家 ECMAScript 6 Node.js CSS 江湖人称“云小梦”。一个大前端路上还未“毕业”的“小学生”。爱好分享、执着探索、乐于开源；曾参与过中大型微信小程序项目前端开发，并主导过一些官网（原生）开发；着迷于vue、node、css以及原生js技术。热衷研究现有技术的成型创新应用。目前对前端可视化和webRTC、web安全有浓厚的兴趣。开源且目前维护的有：微信小程序扩展组件库—— https://github.com/1314mxc/yunUI ，欢迎star！