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:

- Picking a random number from the list (n operations to figure out how long the linked list is)
- 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
next?: Link = null
constructor(val: any) {
this.val = val
}
setNext (node: Link) {
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 ) {
return new Link(1)
} else {
return new Link(length).setNext(constructList(length - 1))
}
}
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)
function listToArray (list: Link): Link[] {
if (list.next === null) {
return [list]
} else {
const currentLink = list
const nextLink = currentLink.next
currentLink.next = null
return [currentLink].concat(listToArray(nextLink))
}
}
function randomizeTimeEfficient (list: Link) {
const arrayFormat = listToArray(list)
return randomizeTimeEfficientRecursive(arrayFormat)
}
function randomizeTimeEfficientRecursive (list: Link[], current?: Link) {
const length = list.length
if (length === 0) {
return current
}
const randomIndex = Math.round(Math.random() * length)
const randomLink = list[randomIndex]
// Construct a list without the randomIndex
const nextList = list.slice(0, randomIndex).concat(list.slice(randomIndex + 1))
if (current) {
current.setNext(randomizeTimeEfficientRecursive(nextList, randomLink))
return current
} else {
return randomizeTimeEfficientRecursive(nextList, randomLink)
}
}
```

### — Option 2 – Space Efficient

**Unfortunately, I did not have time today to complete this algorithm. Instead of working on my next daily coding problem, I will try and complete this one and then update this post accordingly.**