Skip to main content

Clone a linked list with random fields in ruby

Ruby program for Clone a linked list with random fields. Here problem description and other solutions.

#  Ruby Program
#  Clone a linked list with next and random field

#  Linked List Node
class LinkNode 
	# Define the accessor and reader of class LinkNode
	attr_reader :data, :next, :random
	attr_accessor :data, :next, :random
	def initialize(data) 
		#  Set node value
		self.data = data
		self.next = nil
		self.random = nil
	end

end

class MyLinkedList 
	# Define the accessor and reader of class MyLinkedList
	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  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 linked list element
	def display() 
		if (self.head == nil) 
			print("\nEmpty linked list\n")
			return
		end

		temp = self.head
		print("\n ")
		while (temp != nil) 
			if (temp != self.head) 
				print("--->")
			end

			if (temp.random != nil) 
				print(temp.data ,"(", temp.random.data ,")")
			else
 
				print(temp.data)
			end

			temp = temp.next
		end

		print("-->NULL\n")
	end

	#  Clone the linked list  with next and random field
	def cloneList() 
		if (self.head == nil) 
			return nil
		end

		#  Define some auxiliary variable
		temp = nil
		current = self.head
		node = nil
		front = nil
		#  Step 1
		#  Create and combine clone node
		while (current != nil) 
			# Get current node of actual linked list
			temp = current
			#  Create clone node
			node = LinkNode.new(current.data)
			#  Visit to next node
			current = current.next
			#  Connect clone node after actual node
			temp.next = node
			#  Binding this clone to next upcoming
			#  nodes in actual linked list
			node.next = current
		end

		#  Start to actual linked list
		current = self.head
		#  Step 2
		#  Set actual value of random field in clone linked list
		while (current != nil && current.next != nil) 
			#  Clone list node
			node = current.next
			if (current.random != nil) 
				#  Set random node in clone linked list
				node.random = current.random.next
			end

			#  Visit to actual linked list next node
			current = node.next
		end

		#  Agian start to actual linked list
		current = self.head
		#  Step 3
		#  Separate actual and clone linked list
		while (current != nil) 
			node = current.next
			if (front == nil) 
				#  Get first node of clone linked list
				front = node
			end

			current.next = node.next
			current = current.next
			if (current != nil) 
				node.next = current.next
			else
 
				node.next = nil
			end

		end

		return front
	end

end

def main() 
	#  Test linked list
	list1 = MyLinkedList.new()
	list2 = MyLinkedList.new()
	#  Create Normal linked list
	list1.insert(5)
	list1.insert(6)
	list1.insert(1)
	list1.insert(8)
	list1.insert(7)
	#   Simple linked list
	#   5 → 6 → 1 → 8 → 7 → NULL
	#   Set random node value
	#   ╷───────────┐
	#   │           │
	#   │   ╷───────│───┐
	#   ↓───│───╷   │   │
	#   ↓   ↓   ↑   │   │
	#   5 → 6 → 1 → 8 → 7 → NULL
	#   │   │       ↑   │
	#   └───│───────┘   │    
	#       │           │
	#       └───────────┘ 
	#    5(8)-->6(7)-->1(5)-->8(5)-->7(6)-->NULL
	#    Linked list with random field
	#  5-->8
	list1.head.random = list1.head.next.next.next
	#  6-->7
	list1.head.next.random = list1.head.next.next.next.next
	#  1 --> 5
	list1.head.next.next.random = list1.head
	#  8 --> 5
	list1.head.next.next.next.random = list1.head
	#  7 --> 6
	list1.head.next.next.next.next.random = list1.head.next
	list2.head = list1.cloneList()
	print("\n Actual Linked List")
	list1.display()
	print("\n Clone Linked List")
	list2.display()
end

main()

Output

 Actual Linked List
 5(8)--->6(7)--->1(5)--->8(5)--->7(6)-->NULL

 Clone Linked List
 5(8)--->6(7)--->1(5)--->8(5)--->7(6)-->NULL




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