blob: 31df520db8941f3fd669de5f03121bfd4fd81f73 (
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
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
#!perl
################################################################################
=comment
Perl Weekly Challenge 059
=========================
Task #1
-------
*Linked List*
*Reviewed by Ryan Thompson*
You are given a linked list and a value _k_. Write a script to partition the
linked list such that all nodes less than _k_ come before nodes greater than or
equal to _k_. Make sure you preserve the original relative order of the nodes in
each of the two partitions.
For example:
Linked List: 1 → 4 → 3 → 2 → 5 → 2
_k_ = 3
Expected Output: 1 → 2 → 2 → 4 → 3 → 5.
=cut
################################################################################
#--------------------------------------#
# Copyright © 2020 PerlMonk Athanasius #
#--------------------------------------#
use strict;
use warnings;
use LinkedList::Single;
#-------------------------------------------------------------------------------
BEGIN
#-------------------------------------------------------------------------------
{
$| = 1;
print "\n";
}
#===============================================================================
MAIN:
#===============================================================================
{
print "Challenge 059, Task #1: Linked List (Perl)\n";
while (my $line = <DATA>)
{
my ($k, @values) = split /\s+/, $line;
my $origl_list = LinkedList::Single->new(@values);
my $partd_list = partition($origl_list, $k);
printf "\nOriginal list: %s\n", sprint_list($origl_list);
printf "Partitioned on k = %d: %s\n", $k, sprint_list($partd_list);
}
}
#-------------------------------------------------------------------------------
sub partition
#-------------------------------------------------------------------------------
{
my ($list, $k) = @_;
my $left = LinkedList::Single->new;
my $right = LinkedList::Single->new;
$list->head;
while (my @data = $list->each)
{
($data[0] < $k ? $left : $right)->push( @data );
}
$right->head;
while (my @data = $right->each)
{
$left->push( @data );
}
return $left;
}
#-------------------------------------------------------------------------------
sub sprint_list
#-------------------------------------------------------------------------------
{
my ($list) = @_;
my @array;
$list->head;
while (my @data = $list->each)
{
push @array, @data;
}
return sprintf '%s', join ' -> ', @array;
}
################################################################################
#-------------------------------------------------------------------------------
# Sample data with format: _k_ followed by the linked list values
#-------------------------------------------------------------------------------
__DATA__
3 1 4 3 2 5 2
4 1 4 3 2 5 2
5 1 4 3 2 5 2
3 1 2 3 2 1
4 5 4 3 2 1
3 3 6 2 2 1 -1 17 5
0 5 4 3 2 1 0 -1 -2 -3 -4 -5
1 5 4 3 2 1 0 -1 -2 -3 -4 -5
|
