Combine Blockchains

You became a developer because you want to change the world, and you think you found a way to do it.

You discovered two blockchains (SkilledChain and DevCoin) that by being combined, would create a new unified blockchain that will transform every industry. It would enable the infrastructure for a decentralized internet and its cryptocurrency would remove the need for banks and financial institutions.

To validate your hypothesis, you need to create a combined blockchain ordered by when the blocks were created. The nodes for each blockchain have a timestamp property which is the unix timestamp of when the node was added. If there are duplicate timestamps, then either node can come first.

Given the head nodes of two blockchains (represented as linked lists) sorted by a timestamp property, write a function combineBlockchains that returns the head node of a merged linked list that is sorted by timestamp in ascending order.

A blockchain is a great example of a real-life use case for a linked list. Most blockchains behave as a doubly linked list where each node points to the node in front of it and behind it. They also store a of the blocks they point to which ensures the data can exist publicly without fear of it being modified.

Since blockchains are distributed, being able to simply and quickly append a new node to the tail and only needing to update a pointer is a huge benefit.

We see other data structures much more frequently in our day-to-day jobs, so it's good to have an appreciation for how linked lists can also be used practically with a tangible, real-world application.

Breakdown

Follow teacher

Table of Contents

Validate My Answer

Since we know each blockchain has multiple transactions (and therefore nodes), we don't need to worry about empty linked lists. We also know that the timestamp will be an integer >= 0 since they are unix timestamps.
You want to return the head node of the combined list, so make sure you track that correctly. Also make sure this node doesn't appear in the list more than once.
There is a recursive solution which is O(n) time, but this incurs O(n) space from the call stack.
There is an iterative solution that follows similar logic as the recursive solution and is also O(n) time. It improves the space to be constant O(1).
You will need to track 4 pointers: the head for the combined list that is returned, the tail for the combined list for appends, and the first unused node from both of the input blockchains.

Follow teacher

Table of Contents

Test Results

Run your code and see results here...

/**
 * @param {Node} chainHead1
 * @param {Node} chainHead2
 * @return {Node}
 */
const combineBlockchains = (chainHead1, chainHead2) => {
  // Your solution here
};

Combine Blockchains

You became a developer because you want to change the world, and you think you found a way to do it.

/**
 * @param {Node} chainHead1
 * @param {Node} chainHead2
 * @return {Node}
 */
const combineBlockchains = (chainHead1, chainHead2) => {
  // Your solution here
};