#7

Day 7

Photo by Glenn Carstens-Peters on Unsplash

The Problem

Given a linked list, uniformly shuffle the nodes. What if we want to prioritize space over time?

https://dailycodingproblem.com

The Thought Process

Given the problem’s instructions, it was assumed that the linked list was not circular, and therefore had an end element.

When trying to figure out the solution to this problem, I first searched the internet for ways to “uniformly” shuffle an array. I came across this stackoverflow question, which led me to the Fisher—Yates shuffle. This algorithm shuffles all the elements in-place, which makes it quite space-efficient.

— Option 1

Next, I considered the different ways in which the linked list could be optimized in order to take the least time. My first thought was that it would make the whole process quicker if I could get it out of the form of a linked list and into an object format to make fetching each node much faster. The algorithm might look something like this:

1. Turn the linked list into an object data structure (n operations)
2. Shuffle the linked list (n operations)
3. Turn the object back into a linked list (n operations)

The number of operations required would total to: 3n

— Option 2

The alternative option would be to go through the linked list each time. It might look something like this:

1. Picking a random number from the list (n operations to figure out how long the linked list is)
2. Taking a random element from the list and moving it to the end ([n(n+1)]/2 operations)

The number of operations required would total to: [n^2+3n]/2

Comparing the two options

To find out which option would be more efficient at different linked list lengths, I plugged the equations into desmos:

And found that when the list contained less than 3 nodes, option 2 was more efficient, but as soon as the number of nodes passed 3, the first option was more efficient. That being said, option 1 is much less space efficient.

In solving the problem, I plan on writing both algorithms so as to provide code samples of each one.

Shared Code

First, I wrote the code that would be shared between both options. This includes the “Link” class (since `Node` is reserved in TypeScript), a helper function `constructList` that constructs a linked list of a given length, and another helper function `printList` that prints the list values using arrows (for debug purposes).

``````class Link {
val?: any

constructor(val: any) {
this.val = val
}

this.next = node
return this
}
}

function constructList (length: number) {
if (length < 1) {
throw new Error('Length cannot be less than 1')
} else if (length === 1 ) {
} else {
}
}

function printList (list: Link, message = '') {
if (list.next === null) {
console.log(`\${message}\${list.val}`)
} else {
message += `\${list.val} -> `
printList(list.next, message)
}
}``````

The Solutions

— Option 1 – Time Efficient

``````const list = constructList(100)

if (list.next === null) {
return [list]
} else {
}
}

const arrayFormat = listToArray(list)
return randomizeTimeEfficientRecursive(arrayFormat)
}

const length = list.length

if (length === 0) {
return current
}

const randomIndex = Math.round(Math.random() * length)
// Construct a list without the randomIndex
const nextList = list.slice(0, randomIndex).concat(list.slice(randomIndex + 1))

if (current) {