Skip to main content

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




Comment

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