-
Notifications
You must be signed in to change notification settings - Fork 34
/
linked-list-delete-node.py
62 lines (52 loc) · 1.51 KB
/
linked-list-delete-node.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
#Delete node from link list
#Inspiration
#https://medium.com/@bartobri/applying-the-linus-tarvolds-good-taste-coding-requirement-99749f37684a#.ne8bqover
import sys
sys.path.append("../mylib/")
import LinkedListLibrary
class LLNode:
def __init__(self,data):
self.data = data
self.next = None
#Solution 1: return head node
#Assumption: target node is always there!
def deleteNode(node,target):
prev = None
headNode = node #keep track of the head node
while node != target:
prev = node
node = node.next
if prev:
prev.next = node.next
else:
#Head node since prev is None!
headNode = node.next
return headNode
#Solution 2: No return
#Assumption: target node is always there!
def deleteNode2(node,target):
prev = None
while node != target:
prev = node
node = node.next
if prev: #not head node
prev.next = node.next
elif node.next: #head node with next node
assert prev is None, "logic error"
tmp = node.next #reference to next node
node.data = node.next.data #deep copy next node
node.next = node.next.next #deep copy next node
tmp.next = None #remove references to next node
else:
node = None #head node ONLY
head1 = LLNode(1)
head2 = head1
for i in range(2,6):
newNode = LLNode(i)
if i == 3:
head2 = newNode
LinkedListLibrary.Insert2End(head1,newNode)
LinkedListLibrary.PrintLinkedList(head1)
print("node to delete >>>", head2.data)
deleteNode2(head1,head2)
LinkedListLibrary.PrintLinkedList(head1)