Skip to main content

Rotate a linked list by k nodes in ruby

Ruby program for Rotate a linked list by k nodes. Here problem description and other solutions.

#  Ruby program for
#  Rotate 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, :tail
	attr_accessor :head, :tail
	def initialize() 
		self.head = nil
		self.tail = nil
	end

	#  Add new node at the end of linked list
	def insert(value) 
		#  Create a new node
		node = LinkNode.new(value)
		if (self.head == nil) 
			self.head = node
		else
			self.tail.next = node
		end
		self.tail = node
	end

	#  Display linked list element
	def display() 
		if (self.head == nil) 
			return
		end

		temp = self.head
		#  iterating linked list elements
		while (temp != nil) 
			print(temp.data ," → ")
			#  Visit to next node
			temp = temp.next
		end

		print("NULL\n")
	end

	def validKNode(k) 
		temp = self.head
		count = 0
		#  Count node
		while (temp != nil) 
			count += 1
			if (count > k) 
				#  When K is correct
				return k
			end

			#  Visit to next node
			temp = temp.next
		end

		#  Need to change k value
		return k % count
	end

	def rotate(k) 
		if (k <= 0) 
			return
		end

		if (self.head == nil) 
			print("Empty linked list\n")
			return
		end

		#  Assume that k is less the number of nodes
		#  Otherwise first count number of nodes 
		#  Then use modulo operator and change k = k % count
		#  Here implement
		k = self.validKNode(k)
		if (k == 0) 
			#  because after rotate get same result
			return
		else
 
			#  Use to find the location of rotate node
			counter = 1
			point = nil
			temp = self.head
			#  Find last node in rotation
			while (temp != nil && temp.next != nil) 
				if (counter == k) 
					point = temp
				end

				counter += 1
				temp = temp.next
			end

			#  When roated node are exist
			if (point != nil) 
				#  Modified node position
				temp.next = self.head
				#  Modified head
				self.head = point.next
				#  Modified tail
				self.tail = point
				point.next = nil
			end

		end

	end

end

def main() 
	sll = SingleLL.new()
	k = 3
	#  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)
	sll.insert(8)
	print("Before Rotate ", k ," Nodes\n")
	sll.display()
	#  Rotate node
	sll.rotate(k)
	print("After Rotate ", k ," Nodes\n")
	sll.display()
end

main()

Output

Before Rotate 3 Nodes
1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
After Rotate 3 Nodes
4 → 5 → 6 → 7 → 8 → 1 → 2 → 3 → 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