FilesExpand file tree

master

/

remove_duplicates.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

67 lines (59 loc) · 1.22 KB

master

/

remove_duplicates.py

Copy path

Top

File metadata and controls

• Code
• Blame

67 lines (59 loc) · 1.22 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

class Node():

def __init__(self, val = None):

self.val = val

self.next = None

def removeDups(head):

"""

Time Complexity: O(N)

Space Complexity: O(N)

"""

hashset = set()

prev = Node()

while head:

if head.val in hashset:

prev.next = head.next

else:

hashset.add(head.val)

prev = head

head = head.next

def removeDupsWithoutSet(head):

"""

Time Complexity: O(N^2)

Space Complexity: O(1)

"""

current = head

while current:

runner = current

while runner.next:

if runner.next.val == current.val:

runner.next = runner.next.next

else:

runner = runner.next

current = current.next

def printLinkedList(head):

string = ""

while head.next:

string += head.val + " -> "

head = head.next

string += head.val

print(string)

# A A B C D C F G

a1 = Node("A")

a2 = Node("A")

b = Node("B")

c1 = Node("C")

d = Node("D")

c2 = Node("C")

f = Node("F")

g = Node("G")

a1.next = a2

a2.next = b

b.next = c1

c1.next = d

d.next = c2

c2.next = f

f.next = g

removeDups(a1)

printLinkedList(a1)

removeDupsWithoutSet(a1)

printLinkedList(a1)