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
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
<<-DOC
Note: Your solution should have O(n) time complexity, where n is the number of element in l, and O(1) additional space complexity, since this is what you would be asked to accomplish in an interview.
Given a linked list l, reverse its nodes k at a time and return the modified list. k is a positive integer that is less than or equal to the length of l. If the number of nodes in the linked list is not a multiple of k, then the nodes that are left out at the end should remain as-is.
You may not alter the values in the nodes - only the nodes themselves can be changed.
Example
For l = [1, 2, 3, 4, 5] and k = 2, the output should be
reverseNodesInKGroups(l, k) = [2, 1, 4, 3, 5];
For l = [1, 2, 3, 4, 5] and k = 1, the output should be
reverseNodesInKGroups(l, k) = [1, 2, 3, 4, 5];
For l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] and k = 3, the output should be
reverseNodesInKGroups(l, k) = [3, 2, 1, 6, 5, 4, 9, 8, 7, 10, 11].
Input/Output
[time limit] 4000ms (rb)
[input] linkedlist.integer l
A singly linked list of integers.
Guaranteed constraints:
1 ≤ list size ≤ 104,
-109 ≤ element value ≤ 109.
[input] integer k
The size of the groups of nodes that need to be reversed.
Guaranteed constraints:
1 ≤ k ≤ l size.
[output] linkedlist.integer
The initial list, with reversed groups of k elements.
DOC
describe "#reverse_nodes_in_k_groups" do
def length_of(head)
i = 1
i += 1 while head = head.next
i
end
def reverse(head, k)
new_root = nil
root = head
while root && k > 0
next_node = root.next
root.next = new_root
new_root = root
root = next_node
k -= 1
end
new_root
end
def reverse_nodes_in_k_groups(head, k)
return head if k == 1
ph = nil
result = nil
loop do
tail = head
(k - 1).times { tail = tail.next if tail.next }
nh = tail.next
length = length_of(head)
break if k > length
reverse(head, k)
head.next = nh
ph.next = tail if ph
ph = head
head = nh
result = tail if result.nil?
break if head.nil?
end
result
end
[
{ l: [1, 2, 3, 4, 5], k: 2, x: [2, 1, 4, 3, 5] },
{ l: [1, 2, 3, 4, 5], k: 1, x: [1, 2, 3, 4, 5] },
{ l: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11], k: 3, x: [3, 2, 1, 6, 5, 4, 9, 8, 7, 10, 11] },
{ l: [239], k: 1, x: [239] },
{ l: [1, 2, 3, 4], k: 2, x: [2, 1, 4, 3] },
{ l: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], k: 3, x: [3, 2, 1, 6, 5, 4, 9, 8, 7, 12, 11, 10] },
{ l: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12], k: 4, x: [4, 3, 2, 1, 8, 7, 6, 5, 12, 11, 10, 9] },
{ l: [1000000000, -849483855, -1000000000, 376365554, -847904832], k: 4, x: [376365554, -1000000000, -849483855, 1000000000, -847904832] },
{ l: [376365554, -340557143, -849483855, 810952169, -847904832], k: 4, x: [810952169, -849483855, -340557143, 376365554, -847904832] },
{ l: [810952169, -849483855, -340557143, 376365554, -847904832], k: 2, x: [-849483855, 810952169, 376365554, -340557143, -847904832] },
{ l: [-503549928, -526666356, 262916773, -508129645, 992040586, 867794712, 24042453, -540165420, -417669299, 766910780], k: 2, x: [-526666356, -503549928, -508129645, 262916773, 867794712, 992040586, -540165420, 24042453, 766910780, -417669299] },
{ l: [-526666356, -503549928, -508129645, 262916773, 867794712, 992040586, -540165420, 24042453, 766910780, -417669299], k: 8, x: [24042453, -540165420, 992040586, 867794712, 262916773, -508129645, -503549928, -526666356, 766910780, -417669299] },
{ l: [24042453, -540165420, 992040586, 867794712, 262916773, -508129645, -503549928, -526666356, 766910780, -417669299], k: 6, x: [-508129645, 262916773, 867794712, 992040586, -540165420, 24042453, -503549928, -526666356, 766910780, -417669299] },
].each do |x|
it do
result = reverse_nodes_in_k_groups(ListNode.to_list(x[:l]), x[:k]).to_a
expect(result).to eql(x[:x])
end
end
class ListNode
attr_accessor :value, :next
def initialize(value, next_node: nil)
@value = value
@next = next_node
end
def to_a
result = []
current = self
until current.nil?
result.push(current.value)
current = current.next
end
result
end
def self.to_list(items)
x = nil
items.inject(nil) do |memo, item|
node = new(item)
if memo.nil?
x = node
else
memo.next = node
end
node
end
x
end
end
end
|
