Detect and remove loop of linked list in ruby
Ruby program for Detect and remove loop of linked list. Here problem description and other solutions.
# Ruby program for
# Detect and remove loop in a linked list
# Linked list node
class LinkNode
# Define the accessor and reader of class LinkNode
attr_reader :data, :next
attr_accessor :data, :next
def initialize(data)
self.data = data
self.next = nil
end
end
class SingleLL
# Define the accessor and reader of class SingleLL
attr_reader :head
attr_accessor :head
def initialize()
self.head = nil
end
# Add new node at the end of linked list
def insert(value)
# Create a node
node = LinkNode.new(value)
if (self.head == nil)
self.head = node
else
temp = self.head
# Find last node
while (temp.next != nil)
# Visit to next node
temp = temp.next
end
# Add node at last position
temp.next = node
end
end
# Display all Linked List elements
def display()
if (self.head != nil)
temp = self.head
while (temp != nil)
# Display node value
print(" ", temp.data)
# Visit to next node
temp = temp.next
end
else
print("Empty Linked list\n")
end
end
# Delete loop
def deleteLoop(temp)
# Base condition
if (temp == nil || temp.next == nil)
return nil
end
hold = temp.next
# Important to break recursion
temp.next = nil
temp.next = self.deleteLoop(hold)
return temp
end
# Detecting loop of linked list
def detectLoop()
if (self.head == nil)
print("Empty Linked List \n")
return
end
first = self.head
second = self.head
while (second != nil &&
second.next != nil &&
second.next.next != nil)
# Visit to next node
first = first.next
# Visit to second next node
second = second.next.next
if (first == second)
# loop is found
print("Loop Found\n")
# Then delete loop
self.deleteLoop(self.head)
return
end
end
# When no loop
print("Loop not exist\n")
end
end
def main()
sll = SingleLL.new()
# Linked list
# 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
sll.insert(1)
sll.insert(2)
sll.insert(3)
sll.insert(4)
sll.insert(5)
sll.insert(6)
sll.insert(7)
# Case A
# When no loop
sll.detectLoop()
# Create loop for testing
sll.head.next.next.next.next.next.next.next = sll.head.next
# Case B
# When loop
sll.detectLoop()
print("Linked List\n")
# After remove loop, linked list is
sll.display()
end
main()
Output
Loop not exist
Loop Found
Linked List
1 2 3 4 5 6 7
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment