03无序链表中移除重复项

• • 题目描述（难度：中等）
  • 单链表结构
  • 方法一
  • • 复杂度分析
  • 主函数
  • 参考文献

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

class LNode:
    def __init__(self):
        self.data = None # 数据域
        self.next = None # 指针域

• 由于单链表中每个结点的地址都存储在其前驱结点的指针域中，因此，对单链表中任何一个结点的访问只能从链表的头指针开始进行遍历。
• 注意：在修改结点指针域的时候，记录下后继结点的地址，否则会丢失后继结点。

# 对带头结点的无序单链表删除重复的结点 
def removeDup(head):
    if head == None or head.next == None:
        return
    outerCur = head.next  # 用于外层循环，指向链表第一个结点
    innerCur = None  # 用于内层循环用来遍历outerCur后面的结点
    innerPre = None  # innerCur的前驱结点
    while outerCur != None:
        innerCur = outerCur.next
        innerPre = outerCur
        while innerCur != None:
            # 找到重复的结点并删除
            if outerCur.data == innerCur.data:
                innerPre.next = innerCur.next
                innerCur = innerCur.next
            else:
                innerPre = innerCur
                innerCur = innerCur.next
        outerCur = outerCur.next

• 时间复杂度为 O ( n 2 ) O(n^2) O(n2)
• 空间复杂度为 O ( 1 ) O(1) O(1)

if __name__ == "__main__":
    i = 1
    head = LNode()
    head.next = None
    cur = head
    for i in range(1,7):
        tmp = LNode()
        if i % 2 == 0:
            tmp.data = i + 1
        elif i % 3 == 0:
            tmp.data = i - 2
        else:
            tmp.data = i
        tmp.next = None
        cur.next = tmp
        cur = tmp
        i += 1

    print("删除重复结点前：", end='')
    cur = head.next
    while cur != None:
        print(cur.data, '', end='')
        cur = cur.next
    removeDup(head)
    print("n删除重复结点后：", end='')
    cur = head.next
    while cur != None:
        print(cur.data, '', end='')
        cur = cur.next

[1] 何海涛. 剑指Offer：名企面试官精讲典型编程题（第2版）. 北京： 电子工业出版社，2017
[2] 张波，楚秦. Python程序员面试算法宝典. 北京：机械工业出版社，2018