pyAlgoDataStructures/reverseLinkedList.py at master · MFry/pyAlgoDataStructures · 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
class Node:
    def __init__(self, value):
        self._value = value
        self._next_node = None

    @property
    def value(self):
        return self._value

    @value.setter
    def value(self, x):
        self._value = x

    @property
    def next_node(self):
        return self._next_node

    @next_node.setter
    def next_node(self, node):
        self._next_node = node


class LinkedList:

    def __init__(self, val=None):
        if val:
            self._set_first(val)
        else:
            self._head = None
            self._tail = None
            self._length = 0

    def _set_first(self, val):
        self._head = Node(val)
        self._tail = self._head
        self._length = 1

    @property
    def tail(self):
        """

        :return: Returns the last node in the linked list
        :rtype: Node
        """
        return self._tail

    @tail.setter
    def tail(self, node):
        self._tail = node

    @property
    def head(self):
        """

        :return: Linked List Starting Value
        :rtype: Node
        """
        return self._head

    @head.setter
    def head(self, node):
        self._head = node

    def add(self, val):
        n = Node(val)
        if not self.head:
            self._set_first(val)
        else:
            self.tail.next_node = n
            self.tail = n
            self._length += 1

    def __len__(self):
        return self._length


def reverse_list(linked_list):
    current_node = linked_list.head
    prev_node = None
    while current_node is not None:
        t = current_node.next_node
        current_node.next_node = prev_node
        current_node, prev_node = t, current_node
    linked_list.head = prev_node
    return linked_list


def main():
    empty = LinkedList()
    print('LinkedList is empty', len(empty) == 0)
    one_node = LinkedList(2)
    print('Head and tail match and length is 1', one_node.head == one_node.tail and len(one_node) == 1)
    several_nodes = LinkedList()
    several_nodes.add(1)
    several_nodes.add(2)
    several_nodes.add(3)
    several_nodes.add(4)
    print('Length is 4', len(several_nodes) == 4)
    n = several_nodes.head
    while n is not None:
        print('Node val:', n.value)
        n = n.next_node
    reverse_list(several_nodes)
    n = several_nodes.head
    while n is not None:
        print('Node val:', n.value)
        n = n.next_node


if __name__ == '__main__':
    main()