首页 > 代码库 > 链表操作 -- 未排序链表的处理问题

链表操作 -- 未排序链表的处理问题

问题:

  删除未排序链表中的重复元素。

 

解答:

  1)最朴素的方法就是将链表排序,然后遍历并删除其中的重复元素。这种方法的时间复杂度依赖于排序的过程。

  在此,我们要思考一下,找到并且删除链表中的重复元素真的需要排序过程吗?

  

  2)如何才能在不排序的情况下找到重复元素?

    最朴素的方法就是处理每个节点的时候,遍历剩余的节点,查看其中是否有重复的元素。这种方法的时间复杂度较高,O(n2)。

    有没有更好的算法或是数据结构来帮助我们降低这个时间复杂度?这种查找某个元素的存在性问题,可以借助于hash表来快速的实现。由此,算法的时间复杂度降低为了O(n)。

 

 

    

链表操作 -- 未排序链表的处理问题