当前位置: 代码迷 >> 综合 >> 剑指offer之O(1)删除单链表节点
  详细解决方案

剑指offer之O(1)删除单链表节点

热度:7   发布时间:2024-01-16 23:50:07.0

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是否在链表中,只能假设输入无误

  相关解决方案