python-data-structures-and-algorithms/src/data_structures/linked_list/skip_delete.py at master · joaomh/python-data-structures-and-algorithms · 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
"""
You are given the head of a linked list and two integers, 'i' and 'j'.
You have to retain the first 'i' nodes and then delete the next 'j' nodes.
Continue doing so until the end of the linked list.

Example:
'linked-list = 1 2 3 4 5 6 7 8 9 10 11 12'
'i = 2'
'j = 3'
'Output = 1 2 6 7 11 12'
"""
# LinkedList Node class for your reference
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def skip_i_delete_j(head, i, j):
    """
    :param: head - head of linked list
    :param: i - first `i` nodes that are to be skipped
    :param: j - next `j` nodes that are to be deleted
    return - return the updated head of the linked list
    """

    input_node = head
    trim_link_list = None

    position_counter = 1
    i_mode = True
    last_node = False

    while not last_node:
        if i_mode:  # Additive mode
            if trim_link_list is None:
                trim_link_list = Node(input_node.data)
            else:
                position_tail = trim_link_list
                while position_tail.next:  # Moving to the end of the list
                    position_tail = position_tail.next
                position_tail.next = Node(input_node.data)

            if position_counter == i:
                i_mode = False
                position_counter = 0

        else:  # Non-additive mode
            if position_counter == j:
                i_mode = True
                position_counter = 0

        position_counter += 1
        last_node = input_node.next is None
        input_node = input_node.next

    return trim_link_list

# helper functions for testing purpose
def create_linked_list(arr):
    if len(arr)==0:
        return None
    head = Node(arr[0])
    tail = head
    for data in arr[1:]:
        tail.next = Node(data)
        tail = tail.next
    return head

def print_linked_list(head):
    while head:
        print(head.data, end=' ')
        head = head.next
    print()

def test_function(test_case):
    head = test_case[0]
    i = test_case[1]
    j = test_case[2]
    solution = test_case[3]

    temp = skip_i_delete_j(head, i, j)
    index = 0
    try:
        while temp is not None:
            if temp.data != solution[index]:
                print("Fail")
                return
            index += 1
            temp = temp.next
        print("Pass")
    except Exception:
        print("Fail")

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
i = 2
j = 2
head = create_linked_list(arr)
solution = [1, 2, 5, 6, 9, 10]
test_case = [head, i, j, solution]
test_function(test_case)