剑指offer刷题记录14--删除链表的节点(存有问题)
该系列博客内容主要是《剑指Offer》中的经典题目,结合在刷题过程中见到的一些精彩的解题过程,从而在这里记录下来。代码以Python3实现。剑指offer中的原题应该是这样的
题目分析(通过两种不同的思路来解析这道题)
思路1:在单向链表中删除一个节点,常规的做法是从链表的头节点开始顺序遍历,查找要删除的节点,并在链表中删除,这样做的话时间复杂度为O(n)。
代码如下
思路2: 一般来讲,正常的解法时间都是O(N),因为我们要遍历找到待删除的节点,不得不牺牲O(N)的时间复杂度,那么O(1)是怎么实现的呢?我们可以很方便得到要删除节点的下一个节点。如果我们把下一个节点的内容复制到需要删除的节点上,覆盖原有的内容,再把下一个节点删除,这样是不是相当于把当前的节点删除了?
总结:第二种思路没怎么弄明白,在这耽误了好久,希望有看懂的小伙伴可以在下面给出你们的精彩评论。