当前位置 主页 > 网站技术 > 代码类 >

    python无序链表删除重复项的方法

    栏目:代码类 时间:2020-01-17 18:09

    题目描述:

    给定一个没有排序的链表,去掉重复项,并保留原顺序 如: 1->3->1->5->5->7,去掉重复项后变为:1->3->5->7

    方法:

    顺序删除 递归删除

    1.顺序删除

    由于这种方法采用双重循环对链表进行遍历,因此,时间复杂度为O(n**2)
    在遍历链表的过程中,使用了常数个额外的指针变量来保存当前遍历的结点,前驱结点和被删除的结点,所以空间复杂度为O(1)

    #!/usr/bin/env python3
    # -*- coding: utf-8 -*-
    # @Time  : 2020/1/15 20:55
    # @Author : buu
    # @Software: PyCharm
    # @Blog  :https://blog.csdn.net/weixin_44321080
    class LNode:
      def __init__(self, x):
        self.data = x
        self.next = None
    
    def removeDup(head):
      """
      对带头结点的无序单链表删除重复的结点
      顺序删除:通过双重循环直接在链表上进行删除操作
      即,外层循环用一个指针从第一个结点开始遍历整个链表,内层循环从外层指针指向的下一个结点开始,
      遍历其余结点,将与外层循环遍历到的的指针所指的结点的数据域相同的结点删除
      :param head: 头指针
      :return:
      """
      if head is None or head.next is None:
        return
      outerCur = head.next
      innerCur = None
      innerPre = None
      while outerCur is not None:
        innerCur = outerCur.next
        innerPre = outerCur
        while innerCur is not None:
          if outerCur.data == innerCur.data:
            innerPre.next = innerCur.next
            innerCur = innerCur.next
          else:
            innerPre = innerCur
            innerCur = innerCur.next
        outerCur = outerCur.next
    
    if __name__ == '__main__':
      i = 1
      head = LNode(6)
      tmp = None
      cur = head
      while i < 7:
        if i % 2 == 0:
          tmp = LNode(i + 1)
        elif i % 3 == 0:
          tmp = LNode(i - 2)
        else:
          tmp = LNode(i)
        cur.next = tmp
        cur = tmp
        i += 1
      print("before removeDup:")
      cur = head.next
      while cur is not None:
        print(cur.data, end=' ')
        cur = cur.next
      removeDup(head)
      print("\nafter removeDup:")
      cur = head.next
      while cur is not None:
        print(cur.data, end=' ')
        cur = cur.next

    结果:

    在这里插入图片描述

    2.递归

    此方法与方法一类似,从本质上而言,由于这种方法需要对链表进行双重遍历,所以时间复杂度为O(n**2)
    由于递归法会增加许多额外的函数调用,所以从理论上讲,该方法效率比方法一低

    #!/usr/bin/env python3
    # -*- coding: utf-8 -*-
    # @Time  : 2020/1/15 21:30
    # @Author : buu
    # @Software: PyCharm
    # @Blog  :https://blog.csdn.net/weixin_44321080
    class LNode:
      def __init__(self, x):
        self.data = x
        self.next = None
    def removeDupRecursion(head):
      """
      递归法:将问题逐步分解为小问题,即,对于结点cur,首先递归地删除以cur.next为首
      的子链表中重复的结点;接着删除以cur为首的链表中的重复结点,
      :param head:
      :return:
      """
      if head.next is None:
        return head
      pointer = None
      cur = head
      head.next = removeDupRecursion(head.next)
      pointer = head.next
      while pointer is not None:
        if head.data == pointer.data:
          cur.next = pointer.next
          pointer = cur.next
        else:
          pointer = pointer.next
          cur = cur.next
      return head
    def removeDup(head):
      """
      对带头结点的单链表删除重复结点
      :param head: 链表头结点
      :return:
      """
      if head is None:
        return
      head.next = removeDupRecursion(head.next)
    if __name__ == '__main__':
      i = 1
      head = LNode(6)
      tmp = None
      cur = head
      while i < 7:
        if i % 2 == 0:
          tmp = LNode(i + 1)
        elif i % 3 == 0:
          tmp = LNode(i - 2)
        else:
          tmp = LNode(i)
        cur.next = tmp
        cur = tmp
        i += 1
      print("before recursive removeDup:")
      cur = head.next
      while cur is not None:
        print(cur.data, end=' ')
        cur = cur.next
      removeDup(head)
      print("\nafter recurseve removeDup:")
      cur = head.next
      while cur is not None:
        print(cur.data, end=' ')
        cur = cur.next