"A book to train programming skills to fight in the world" Python code Solution example --2.8 Loop detection
python
from chap2_function import*
def FindBeginning(head_node):
slow = head_node
fast = head_node
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
if fast == None or fast.next == None:
return None
slow = head_node
while slow != fast:
slow = slow.next
fast = fast.next
return fast
sll = SinglyLinkedList()
sll.append(1)
sll.append(2)
sll.append(3)
sll.append(4)
sll.append(5)
sll.printList(sll.head)
sll.insertNode(sll.head.next.next.next.next,sll.head.next.next)
print("sll[0]: ", sll.head.data)
print("sll[1]: ",sll.head.next.data)
print("sll[2]: ",sll.head.next.next.data)
print("sll[3]: ",sll.head.next.next.next.data)
print("sll[4]: ",sll.head.next.next.next.next.data)
print("sll[5]: ",sll.head.next.next.next.next.next.data)
print("sll[6]: ",sll.head.next.next.next.next.next.next.data)
print("output: ",FindBeginning(sll.head).data)
chap2_function.py
#Node class
class Node:
#constructor
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
#Unidirectional list class
class SinglyLinkedList:
#constructor
def __init__(self):
self.head = None
def insertNode(self, prev_node, new_node):
if prev_node is None:
print("the given previous node cannot be NULL")
return
if new_node is None:
print("the given new node cannot be NULL")
return
# prev_Makes the next node of the node specified by node a new node
prev_node.next = new_node
#Insert node from last node
def append(self, new_data):
#Node generation
new_node = Node(new_data)
#Define the next node of the new node to None
new_node.next = None
#If no head node is set (empty list), set a new node as the head node
if self.head is None:
new_node.prev = None
self.head = new_node
return
#Set the final node (forward scanning)
last = self.head
while(last.next is not None):
last = last.next
#Designate a new node as the last node
last.next = new_node
return
# This function prints contents of linked list
# starting from the given node
def printList(self, node):
last = None
print("Unidirectional list: \n")
print("Forward scanning")
while(node is not None):
print(node.data,end="")
last = node
node = node.next
if node:
print(" -> ",end="")
else:
print("\n")
#Bidirectional list class
class DoublyLinkedList:
#constructor
def __init__(self):
self.head = None
#Node insertion from the first node
def push(self, new_data):
#Node generation
new_node = Node(new_data)
#Make the next node of the new node the head node in the first place
new_node.next = self.head
#Although it was a head node in the first place, the previous node is changed to a new node
if self.head is not None:
self.head.prev = new_node
#Make the new node a head node
self.head = new_node
#Insert node at waypoint
def insert(self, prev_node, new_data):
# prev_Specify whether to insert the node after the node specified by node
#If None, exit the function
if prev_node is None:
print("the given previous node cannot be NULL")
return
#Node generation
new_node = Node(new_data)
#Prev the next node of the new node_Make it the next node of the node specified by node
new_node.next = prev_node.next
# prev_Makes the next node of the node specified by node a new node
prev_node.next = new_node
#Prev the previous node of the new node_Make it the node specified by node
new_node.prev = prev_node
#Prev the next node of the new node_I made it the next node of the node specified by node, but the previous node of that node is also made a new node
if new_node.next is not None:
new_node.next.prev = new_node
def insertNode(self, prev_node, new_node):
# prev_Specify whether to insert the node after the node specified by node
#If None, exit the function
if prev_node is None:
print("the given previous node cannot be NULL")
return
if new_node is None:
print("the given new node cannot be NULL")
return
# prev_Makes the next node of the node specified by node a new node
prev_node.next = new_node
#Prev the previous node of the new node_Make it the node specified by node
new_node.prev = prev_node
#Insert node from last node
def append(self, new_data):
#Node generation
new_node = Node(new_data)
#Define the next node of the new node to None
new_node.next = None
#If no head node is set (empty list), set a new node as the head node
if self.head is None:
new_node.prev = None
self.head = new_node
return
#Set the final node (forward scanning)
last = self.head
while(last.next is not None):
last = last.next
#Designate a new node as the last node
last.next = new_node
# 7.Make the previous node of the new node the last node in the first place
new_node.prev = last
return
def delete(self,del_node):
if self.head == None or del_node == None:
return
if self.head == del_node:
self.head = del_node.next
if del_node.next != None:
del_node.next.prev = del_node.prev
if del_node.prev != None:
del_node.prev.next = del_node.next
# This function prints contents of linked list
# starting from the given node
def printList(self, node):
last = None
print("Bidirectional list: \n")
print("Forward scanning")
while(node is not None):
print(node.data,end="")
last = node
node = node.next
if node:
print(" -> ",end="")
else:
print("\n")
print("Reverse scanning")
while(last is not None):
print(last.data,end="")
last = last.prev
if last:
print(" -> ",end="")
else:
print("\n")
if __name__ == '__main__':
#Generate an empty bidirectional list
# DLL: None
dll = DoublyLinkedList()
# DLL: None -> 6(head/last) -> None
dll.append(6)
# DLL: None -> 7(head) -> 6(last) -> None
dll.push(7)
# DLL: None -> 1(head) -> 7 -> 6(last) -> None
dll.push(1)
# DLL: None -> 1(head) -> 7 -> 6 -> 4(last) -> None
dll.append(4)
# DLL: None -> 1(head) -> 7 -> 8 -> 6 -> 4(last) -> None
dll.insert(dll.head.next, 8)
# DLL: None -> 1(head) -> 8 -> 6 -> 4(last) -> None
dll.delete(dll.head.next)
dll.printList(dll.head)
sll = SinglyLinkedList()
sll.append(1)
sll.append(8)
sll.append(6)
sll.append(4)
sll.printList(sll.head)
[1] GeeksforGeeks: Doubly Linked List | Set 1 (Introduction and Insertion) [2] GeeksforGeeks: Delete a node in a Doubly Linked List