Python-Programming/LinkedList.py at main · fuadhasanemon/Python-Programming · GitHub

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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
from collections import defaultdict


class Node:

    def __init__(self,data):
        self.data = data
        self.nextNode = None

class LinkedList:

    def __init__(self):
        self.head = None

    def insert(self,newNode):
        if self.head is None:
            self.head = newNode

        else:
            lastNode = self.head

            while True:
                if lastNode.nextNode is None:
                    break
                else:
                    lastNode = lastNode.nextNode

            lastNode.nextNode = newNode

    def printList(self):
        startNode = self.head

        while True:
            print(startNode.data)
            if startNode.nextNode is None:
                break
            else:
                startNode = startNode.nextNode

    def getMiddle(self):
        startSlow = self.head
        startFast = self.head

        while True:
            if startFast.nextNode is None:
                break
            else:
                startSlow = startSlow.nextNode
                if startFast.nextNode.nextNode is None:
                    startFast = startFast.nextNode
                else:
                    startFast = startFast.nextNode.nextNode


        print(startSlow.data)

    def length(self):
        x = 0

        startNode = self.head

        while True:
            x = x + 1
            if startNode.nextNode is None:
                break
            else:
                startNode = startNode.nextNode

        print(x)

    def thirdNode(self):

        startNode = self.head

        while True:
            if startNode.nextNode.nextNode.nextNode is None:
                break

            else:

                startNode = startNode.nextNode


        print(startNode.data)


    def findDuplicate(self):

        letterDict = dict()
        startNode = self.head
        x = 0

        while True:
            if startNode is None:
                break

            if startNode.data in letterDict :
                print("Duplicate exists in ",letterDict[startNode.data],x)
                break

            letterDict[startNode.data] = x
            startNode = startNode.nextNode
            x = x + 1


node1 = Node("a")
node2 = Node("b")
node3 = Node("c")
node4 = Node("d")
node5 = Node("e")
node6 = Node("f")
node7 = Node("g")
node8 = Node("b")

linkedList = LinkedList()

linkedList.insert(node1)
linkedList.insert(node2)
linkedList.insert(node3)
linkedList.insert(node4)
linkedList.insert(node5)
linkedList.insert(node6)
linkedList.insert(node7)
linkedList.insert(node8)

linkedList.findDuplicate()