master
1<<-DOC
2Note: 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.
3
4Given 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.
5
6You may not alter the values in the nodes - only the nodes themselves can be changed.
7
8Example
9
10For l = [1, 2, 3, 4, 5] and k = 2, the output should be
11reverseNodesInKGroups(l, k) = [2, 1, 4, 3, 5];
12For l = [1, 2, 3, 4, 5] and k = 1, the output should be
13reverseNodesInKGroups(l, k) = [1, 2, 3, 4, 5];
14For l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11] and k = 3, the output should be
15reverseNodesInKGroups(l, k) = [3, 2, 1, 6, 5, 4, 9, 8, 7, 10, 11].
16Input/Output
17
18[time limit] 4000ms (rb)
19[input] linkedlist.integer l
20
21A singly linked list of integers.
22
23Guaranteed constraints:
241 ≤ list size ≤ 104,
25-109 ≤ element value ≤ 109.
26
27[input] integer k
28
29The size of the groups of nodes that need to be reversed.
30
31Guaranteed constraints:
321 ≤ k ≤ l size.
33
34[output] linkedlist.integer
35
36The initial list, with reversed groups of k elements.
37DOC
38
39describe "#reverse_nodes_in_k_groups" do
40 def length_of(head)
41 i = 1
42 i += 1 while head = head.next
43 i
44 end
45
46 def reverse(head, k)
47 new_root = nil
48 root = head
49
50 while root && k > 0
51 next_node = root.next
52 root.next = new_root
53 new_root = root
54 root = next_node
55 k -= 1
56 end
57
58 new_root
59 end
60
61 def reverse_nodes_in_k_groups(head, k)
62 return head if k == 1
63 ph = nil
64 result = nil
65
66 loop do
67 tail = head
68 (k - 1).times { tail = tail.next if tail.next }
69 nh = tail.next
70 length = length_of(head)
71 break if k > length
72
73 reverse(head, k)
74 head.next = nh
75 ph.next = tail if ph
76 ph = head
77 head = nh
78 result = tail if result.nil?
79 break if head.nil?
80 end
81 result
82 end
83
84 [
85 { l: [1, 2, 3, 4, 5], k: 2, x: [2, 1, 4, 3, 5] },
86 { l: [1, 2, 3, 4, 5], k: 1, x: [1, 2, 3, 4, 5] },
87 { 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] },
88 { l: [239], k: 1, x: [239] },
89 { l: [1, 2, 3, 4], k: 2, x: [2, 1, 4, 3] },
90 { 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] },
91 { 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] },
92 { l: [1000000000, -849483855, -1000000000, 376365554, -847904832], k: 4, x: [376365554, -1000000000, -849483855, 1000000000, -847904832] },
93 { l: [376365554, -340557143, -849483855, 810952169, -847904832], k: 4, x: [810952169, -849483855, -340557143, 376365554, -847904832] },
94 { l: [810952169, -849483855, -340557143, 376365554, -847904832], k: 2, x: [-849483855, 810952169, 376365554, -340557143, -847904832] },
95 { l: [-503549928, -526666356, 262916773, -508129645, 992040586, 867794712, 24042453, -540165420, -417669299, 766910780], k: 2, x: [-526666356, -503549928, -508129645, 262916773, 867794712, 992040586, -540165420, 24042453, 766910780, -417669299] },
96 { l: [-526666356, -503549928, -508129645, 262916773, 867794712, 992040586, -540165420, 24042453, 766910780, -417669299], k: 8, x: [24042453, -540165420, 992040586, 867794712, 262916773, -508129645, -503549928, -526666356, 766910780, -417669299] },
97 { l: [24042453, -540165420, 992040586, 867794712, 262916773, -508129645, -503549928, -526666356, 766910780, -417669299], k: 6, x: [-508129645, 262916773, 867794712, 992040586, -540165420, 24042453, -503549928, -526666356, 766910780, -417669299] },
98 ].each do |x|
99 it do
100 result = reverse_nodes_in_k_groups(ListNode.to_list(x[:l]), x[:k]).to_a
101 expect(result).to eql(x[:x])
102 end
103 end
104
105 class ListNode
106 attr_accessor :value, :next
107
108 def initialize(value, next_node: nil)
109 @value = value
110 @next = next_node
111 end
112
113 def to_a
114 result = []
115 current = self
116 until current.nil?
117 result.push(current.value)
118 current = current.next
119 end
120 result
121 end
122
123 def self.to_list(items)
124 x = nil
125 items.inject(nil) do |memo, item|
126 node = new(item)
127 if memo.nil?
128 x = node
129 else
130 memo.next = node
131 end
132 node
133 end
134 x
135 end
136 end
137end