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. Each node in a blockchain has a data 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 timestamp (the data 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. A blockchain behaves as a singly linked list where each block points only to the block that came before 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

Approach and test strategy

Merge two ordered linked chains without losing a successor

Read the approach, boundary cases, and complexity

Each chain is already ordered by block timestamp and the prompt promises nonempty chains. Repeatedly choose the smaller available head and advance that chain. Preserve the next unprocessed node before changing links. When one chain is exhausted, append the remaining suffix of the other chain; it is already ordered. Equal timestamps still represent distinct blocks and must both remain in the result.

Cases to check

Try one block in each chain and interleaved timestamps.
Put every timestamp from one chain before the other.
Include equal timestamps and a chain that runs out early.

Cost model

Merging m and n nodes takes O(m + n) time. Relinking existing nodes can use constant auxiliary references; allocating copied nodes changes the storage and identity contract.

Programming languages for this lesson

Starter code and reference implementations are available in:

The editor shows which of these languages can run on this deployment.

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 each node's data will be an integer >= 0 since it is a unix timestamp.
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 {ListNode} chainHead1
 * @param {ListNode} chainHead2
 * @return {ListNode}
 */
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 {ListNode} chainHead1
 * @param {ListNode} chainHead2
 * @return {ListNode}
 */
const combineBlockchains = (chainHead1, chainHead2) => {
  // Your solution here
};