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
|
<<-DOC
Note: Your solution should have O(l1.length + l2.length) time complexity, since this is what you will be asked to accomplish in an interview.
Given two singly linked lists sorted in non-decreasing order, your task is to merge them. In other words, return a singly linked list, also sorted in non-decreasing order, that contains the elements from both original lists.
Example
For l1 = [1, 2, 3] and l2 = [4, 5, 6], the output should be
mergeTwoLinkedLists(l1, l2) = [1, 2, 3, 4, 5, 6];
For l1 = [1, 1, 2, 4] and l2 = [0, 3, 5], the output should be
mergeTwoLinkedLists(l1, l2) = [0, 1, 1, 2, 3, 4, 5].
Input/Output
[time limit] 4000ms (rb)
[input] linkedlist.integer l1
A singly linked list of integers.
Guaranteed constraints:
0 ≤ list size ≤ 104,
-109 ≤ element value ≤ 109.
[input] linkedlist.integer l2
A singly linked list of integers.
Guaranteed constraints:
0 ≤ list size ≤ 104,
-109 ≤ element value ≤ 109.
[output] linkedlist.integer
A list that contains elements from both l1 and l2, sorted in non-decreasing order.
DOC
describe "#merge_two_linked_lists" do
def merge_two_linked_lists(left, right)
return left if right.nil?
return right if left.nil?
result, other = left.value < right.value ? [left, right] : [right, left]
current = result
previous = nil
until other.nil?
if current.value < other.value
if current.next
previous = current
current = current.next
else
current.next = other
break
end
elsif current.value == other.value
tmp = other
other = other.next
tmp.next = current.next
current.next = tmp
previous = current
current = current.next
else
tmp = other
other = other.next
tmp.next = current
previous&.next = tmp
previous = tmp
end
end
result
end
[
{ l1: [1, 2, 3], l2: [4, 5, 6], x: [1, 2, 3, 4, 5, 6] },
{ l1: [1, 1, 2, 4], l2: [0, 3, 5], x: [0, 1, 1, 2, 3, 4, 5] },
{ l1: [5, 10, 15, 40], l2: [2, 3, 20], x: [2, 3, 5, 10, 15, 20, 40] },
{ l1: [1, 1], l2: [2, 4], x: [1, 1, 2, 4] },
{ l1: [], l2: [1, 1, 2, 2, 4, 7, 7, 8], x: [1, 1, 2, 2, 4, 7, 7, 8] },
{ l1: [], l2: [], x: [] },
{ l1: [1, 1, 4], l2: [], x: [1, 1, 4] },
{ l1: [1, 1], l2: [0], x: [0, 1, 1] },
{ l1: [0], l2: [2], x: [0, 2] },
{ l1: [1], l2: [-1000000000, 1000000000], x: [-1000000000, 1, 1000000000] },
{ l1: [-1, -1, 0, 1], l2: [-1, 0, 0, 1, 1], x: [-1, -1, -1, 0, 0, 0, 1, 1, 1] },
{ l1: [-780990573, -670826849, -404817961, 242026249, 731519938], l2: [-815817641, -426491047, 437929670, 520408640], x: [-815817641, -780990573, -670826849, -426491047, -404817961, 242026249, 437929670, 520408640, 731519938] },
].each do |x|
it do
result = merge_two_linked_lists(ListNode.to_list(x[:l1]), ListNode.to_list(x[:l2])).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
|
