Partition A Linked List
Suppose we are asked the following: Write a script to partition the linked list such that all nodes less than k come before nodes greater than or equal to k.
For example the linked list: 1 → 4 → 3 → 2 → 5 → 2
with k = 3
would be changed to 1 → 2 → 2 → 4 → 3 → 5.
This question was one of two parts to Perl Weekly Challenge 059. My solution can be outlined as
- Walk the linked list and identify which nodes are less than k.
- Push each of these nodes into an array.
- Each node pushed to the array is also removed from the list.
- The array is sorted by node value (optional).
- The nodes from the array are added to the beginning of the list.
In Perl this is what the above steps look like.
When run with the example above we have the following
$ perl -Iperl perl/ch-1.pl
Original: 1 -> 4 -> 3 -> 2 -> 5 -> 2
Partitioned: 1 -> 2 -> 2 -> 4 -> 3 -> 5
- The main code is in LinkedList.pm, with a small test driver called ch-1.pl. Both are in the GitHub gist linked to by the code excerpt.
- Class::Struct was used for the Linked List itself, as well as the nodes. This way of representing classes in Perl is not as popular as it once was but it is still a favorite of mine. I have used it for past PWC challenges, most relatedly for Priority Queues.
- Also, another core module, Tie::RefHash was used in order to conveniently use the list nodes as hash keys.
Count The Different Bits
Part Two of this week's challenge was a smaller problem involving counting the number of complementary bits in the binary representations of pairs of numbers. The difference counts are all then summed.
- This works by comparing the bit on the far right in each number to each other. This bit is then shifted off and the next bit checked and so on.
- I found this Bitwise Operator Calculator very helpful to refresh my memory on working with bits. It is not something I have done in a long time!