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
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