-
Notifications
You must be signed in to change notification settings - Fork 3
/
rotate_right.rb
117 lines (99 loc) · 2.15 KB
/
rotate_right.rb
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
require_relative './linklist'
# Definition for singly-linked list.
# class ListNode
# attr_accessor :val, :next
# def initialize(val = 0, _next = nil)
# @val = val
# @next = _next
# end
# end
# @param {ListNode} head
# @param {Integer} k
# @return {ListNode}
#
# using length
# def rotate_right(head, k)
# return head if head.nil? || k.zero?
# len = 1
# current_node = head
# while current_node.next
# len += 1
# current_node = current_node.next
# end
# # current_node will be last node
# last_node = current_node
# k = k % len if k > len
# return head if len == 1 || k == len || k.zero?
# count = 0
# node = head
# while count < len - k - 1
# count += 1
# node = node.next
# end
# new_head = node.next
# node.next = nil
# last_node.next = head
# head = new_head
# end
# # using two pointers
# def rotate_right(head, k)
# return nil if head.nil?
# return head if k.zero?
# len = 1
# current_node = head
# while current_node.next
# len += 1
# current_node = current_node.next
# end
# k = k % len if k > len
# return head if len == 1 || k == len || k == 0
# ptr1 = head
# ptr2 = head
# count = 0
# while ptr1
# ptr1 = ptr1.next
# ptr2 = ptr2.next if count > k
# count += 1
# end
# return head if count == k
# new_head = ptr2.next
# ptr2.next = nil
# tail = current_node
# tail.next = head
# head = new_head
# end
def rotate_right(head, k)
return head if head.nil? || k.zero?
len = 1
current_node = head
while current_node.next
len += 1
current_node = current_node.next
end
k = k % len if k > len
return head if len == 1 || k == len || k.zero?
prev = nil
current_node.next = head
current_node = current_node.next
(len - k - 1).times do
prev = current_node
current_node = current_node.next
end
prev.next = nil
current_node
end
def length(head)
return 0 if head.nil?
count = 0
while head
count += 1
head = head.next
end
count
end
ll = LinkList.new([1, 2, 3, 4, 5, 6])
ll.head = rotate_right(ll.head, 1)
puts ll.print
ll = LinkList.new([1])
ll.head = rotate_right(ll.head, 2)
puts ll.print