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
|
#!/usr/bin/perl
# Test: ./ch-1.pl
package LinkedList::Node; # Linked list
use Mouse;
has 'value' => (
is => 'rw',
isa => 'Maybe[Int]',
default => sub {
return undef;
}
);
has 'next' => (
is => 'rw',
isa => 'Maybe[LinkedList::Node]',
default => sub {
return undef
}
);
__PACKAGE__->meta->make_immutable();
package LinkedList;
use Mouse;
use feature qw /say/;
use LinkedList::Node;
has 'first' => (
is => 'rw',
isa => 'Maybe[LinkedList::Node]',
default => sub {
return undef
}
);
# Create the list
sub create_list {
my ($self, @values) = @_;
my $prev_node;
# Populate the list
for my $value (@values) {
my $node = LinkedList::Node->new(value => $value);
# Populate first and next nodes
($prev_node) ?
$prev_node->next($node) :
$self->first($node);
# Next
$prev_node = $node;
}
}
sub partition_list {
my ($self, $k) = @_;
# Loop through the nodes
my $node = $self->first;
my $passed_k = 0;
my $prev_node;
my $k_node;
while ($node) {
my $next_node = $node->next;
my $moved_node = 0;
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 = 1;
}
# 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 = 1;
};
# 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;
}
}
sub display_list {
my $self = shift;
my $node = $self->first;
my @keys;
while ($node) {
push @keys, $node->value;
$node = $node->next;
}
return join ' → ', @keys;
}
__PACKAGE__->meta->make_immutable();
package main;
use strict;
use warnings;
use LinkedList;
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;
|
