blob: 1a4843f812feab1941ed941cc99074ac89239c37 (
plain)
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
|
# Test: perl6 ch-1.p6
class LinkedList::Node {
has Int $.value is rw;
has LinkedList::Node $.next is rw;
}
class LinkedList {
has LinkedList::Node $.first is rw;
# Create the list
method create-list(*@values) {
my $prev_node;
# Populate the list
for @values -> $value {
my $node = LinkedList::Node.new(value => $value);
# Populate first and next nodes
if ($prev_node) {
$prev_node.next = $node
} else {
self.first = $node;
}
# Next node
$prev_node = $node;
}
}
method partition-list(Int $k) {
# Loop through the nodes
my $node = self.first;
my $passed_k = False;
my $prev_node;
my $k_node;
while ($node) {
my $next_node = $node.next;
my $moved_node = False;
if ($node.value < $k && $passed_k) {
my $traverse_node = self.first;
while ($traverse_node.next.value < $node.value) {
$traverse_node = $traverse_node.next;
}
$prev_node.next = $node.next;
$node.next = $traverse_node.next;
$traverse_node.next = $node;
$moved_node = True;
}
# Other k's
if ($node.value == $k && $passed_k) {
my $temp = $k_node.next;
$prev_node.next = $node.next;
$k_node.next = $node;
$node.next = $temp;
$moved_node = True;
};
# First k encountered
if ($node.value == $k && !$passed_k) {
$passed_k = 1;
$k_node = $node;
};
# The prev node pointer only changes if we
# didn't move the node
$prev_node = $node unless ($moved_node);
# Next node
$node = $next_node;
}
}
method display-list {
my $node = self.first;
my @keys;
while ($node) {
@keys.push($node.value);
$node = $node.next;
}
return @keys.join(" → ");
}
}
sub MAIN() {
my $ll = LinkedList.new();
$ll.create-list(1,4,3,2,5,2);
say 'Before: ' ~ $ll.display-list;
$ll.partition-list(3);
say 'After: ' ~ $ll.display-list;
say "\nDuplicate k's";
$ll.create-list(1,4,3,2,5,2,3);
say 'Before: ' ~ $ll.display-list;
$ll.partition-list(3);
say 'After: ' ~ $ll.display-list;
}
|
