-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy pathcodechallenge_015.py
156 lines (132 loc) · 3.99 KB
/
codechallenge_015.py
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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
'''
Date: 12/29/2018
Problem description:
===================
This problem was asked by Google.
Given a singly linked list and an integer k, remove the kth last element from the list.
k is guaranteed to be smaller than the length of the list.
The list is very long, so making more than one pass is prohibitively expensive.
Algorithm:
=========
Input: A linked list
Output: A modified linked list
Psuedo code:
1. Check edge cases
2. Travese the linked list until value k is found
3. Continue by calling a sub-function to travese the rest of the list for more matching k
4. If more found, delete that last found node, else delete the currently matching k node
'''
from __future__ import print_function
import random
class linkedlistNode:
def __init__(self, val, next=None):
self.val = val
self.next = next
#
# add a node to end of linked list
#
def insertNode(head, val):
currNode = head
while currNode is not None:
if currNode.next is None:
currNode.next = linkedlistNode(val)
return head
currNode = currNode.next
#
# print linked list
#
def printNode(head):
retstr = []
curr = head
while curr:
retstr.append(str(curr.val))
#print(curr.val)
curr = curr.next
print(' -> '.join(retstr))
#
# search for node.val == k in
# sub-linked list
#
def isMoreKnode(head, k):
currNode = head
if currNode is None:
return False
currNode = currNode.next
while currNode is not None:
if currNode.val == k:
return True
currNode = currNode.next
return False
#
# Traverse the singly linked list to find
# the last item matching k.
# If found one, call a look-ahead function
# to determine if more match is found further
# up the linked list.
#
def deleteLastKthNode(head, k):
currNode = head
prevNode = None
moreKNode = False
# edge case
if currNode is None or type(k) is not int:
return None
while currNode is not None:
if currNode.val == k:
# found a match, let's see if there is more
moreKNode = isMoreKnode(currNode, k)
if moreKNode == False:
#print("isMoreKnode:{}".format(moreKNode))
# let's delete the last kth node
if prevNode is None:
newHead = currNode.next
return newHead
else:
prevNode.next = currNode.next
return head
# progressing toward end of list
prevNode = currNode
currNode = currNode.next
return head
if __name__ == '__main__':
node = linkedlistNode(3)
insertNode(node,4)
insertNode(node,9)
insertNode(node,8)
insertNode(node,3)
insertNode(node,4)
insertNode(node,7)
k=4
print("Test#1")
print("Original linked list: ", end='')
printNode(node)
print("Deleting the last node having value: {}".format(k))
deleteLastKthNode(node,k)
print("Resulting linked list: ", end='')
printNode(node)
k = 100
nodeX = linkedlistNode(10)
insertNode(nodeX, k)
[insertNode(nodeX, int(10*random.random())) for i in range(15)]
insertNode(nodeX, k)
insertNode(nodeX, k+1)
print("Test#2")
print("Original linked list: ", end='')
printNode(nodeX)
print("Deleting the last node having value: {}".format(k))
deleteLastKthNode(nodeX, k)
print("Resulting linked list: ", end='')
printNode(nodeX)
'''
Run-time output:
===============
markn@raspberrypi3:~/devel/py-src/DailyCodeChallenge $ python3 codechallenge_015.py
Test#1
Original linked list: 3 -> 4 -> 9 -> 8 -> 3 -> 4 -> 7
Deleting the last node having value: 4
Resulting linked list: 3 -> 4 -> 9 -> 8 -> 3 -> 7
Test#2
Original linked list: 10 -> 100 -> 7 -> 2 -> 9 -> 6 -> 5 -> 6 -> 8 -> 4 -> 0 -> 2 -> 7 -> 4 -> 5 -> 4 -> 2 -> 100 -> 101
Deleting the last node having value: 100
Resulting linked list: 10 -> 100 -> 7 -> 2 -> 9 -> 6 -> 5 -> 6 -> 8 -> 4 -> 0 -> 2 -> 7 -> 4 -> 5 -> 4 -> 2 -> 101
'''