Onward with interview prep. If you are unfamiliar with singly linked lists, please read Part 1 as this post will continue from where we left off:
First a quick review:
Note: When I refer to “linked lists,” I am referring to singly linked lists. (There are also doubly linked lists, but we’ll keep them for another time)
Linked lists are like arrays: they are “list-like” objects. The difference is that linked lists do not have indices like arrays. Linked lists have a beginning point( usually called a “head” and an ending point (usually called a “tail”). If you want to access a given element of the list (also called a “node”), you just have to traverse the linked list starting always at the head.
Imagine you are standing on one bank of a river and you want to cross it. There are a series of big rocks that form a bridge across the river. You can now step from one side of the river (the head) across to the other side of the river (the tail). Oh yes, that rock bridge is one-way only!
Ok, that was the review. Now let’s talk about a common algorithm you might be asked in interviews involving linked lists:
Find the Median of the Linked List
We’re given a linked list as pictured above. Our linked list has 5 nodes. Its first node, or head, contains the integer “5”. This node points to “4”. “4” points to “7” and so on. The last node, “10”, points to “null”. Our task is to find out what the median point of the node is.
The brute force way might be to just traverse the list and keep a counter so we can find out how long the list is. When we hit “null” we know we’ve reached the end of the list. Now just divide the counter by 2 and then floor the result if we get a decimal. We can then traverse a second time by “result’s” number of times to find the median.
But let’s impress the interviewer instead. Let’s show him a really sophisticated way of doing this. We’ll use the “Tortoise and Hare” approach attributed to Robert W. Floyd. Let's put both the tortoise and the hare at the head of the linked list. The hare can traverse the list two times as fast as the tortoise. In other words, the tortoise will always only be able to cover half the ground as the hare.
Let’s now let them both start traversing our linked list. The hare will finish first, of course. He will have to stop at the tail of the linked list. But once the hare has reached the end of the linked list, we know the tortoise will have only traversed half as much as the hare. What? “Half as much” means half the length of the link or the middle point!
Now we’ve found the median and we’ve done it so efficiently. Instead of all that counting and extra time traversing twice in our brute force method, we’ve only traversed the list once using “pointers” (the hare and the tortoise).
Have a look at a picture:
Ok, now let’s code it up in JavaScript:
First, let’s recreate our two classes from Part I: First, we'll make a Node class to create individual nodes and second: a SinglyLinkedList class where we’ll put all our methods.
class Node {
constructor(val) {
this.val = val
this.next = next
}
}
class SinglyLinkedList {
constructor() {
this.length = 0
this.head = null
this.tail = null
}
}
Now let’s create the shell of our new findMiddleElement method. We’ll set the variables “tortoise” and “hare” each to the head of the linked list as that is where they will start their "run."
class Node {
constructor(val) {
this.val = val
this.next = next
}
}
class SinglyLinkedList {
constructor() {
this.length = 0
this.head = null
this.tail = null
}
findMiddleElement() {
let tortoise = this.head
let hare = this.head
}
}
The first thing we should do is find out if the list really exists ( Testing for this edge case will show your interviewer that you’re really on your toes!)
One easy way to do this is just check to see if there is a head. If there is no head to the list, then there is no list and we can just return “undefined”. (Ask your interviewer what you should return in this case. Maybe they want something else returned, like “-1” or “Oops!”.
class Node {
constructor(val) {
this.val = val
this.next = next
}
}
class SinglyLinkedList {
constructor() {
this.length = 0
this.head = null
this.tail = null
}
findMiddleElement() {
let tortoise = this.head
let hare = this.head
if(!this.head) {
return undefined
}
}
Next comes the “meat” of our logic. We want our tortoise and hare to start moving along the linked list. However, we don’t know how long our list is, so we should use a “while” loop.
We’ll let our “while” loop run until the hare gets to the end of the list. How will we know when the hare has completed his run? There are two possibilities:
1). If there is an odd number of nodes he'll be at the end of the list when he gets to the very last node We’ll know he’s at the last node when the next node is “null”. For example: in a list that has 7 nodes, he’ll start at node #1, and then moving 2 nodes at a time, he’ll go from node 1 to node 3 to node 5 to node 7. At node 7, the next node is null, he’ll have to stop there. This means our condition for the “while” loop will be “keep going as long as the hare’s “next” node is not “null” (hare.next !== null)
- Now consider if there is an even number of nodes. For example, if there are 8 nodes and our hare starts at node 1, he’ll go node 1 to node 3 to node 5 to node 7. At node 7 when he then jumps 2 nodes, he’ll go off the list and be in “null” land. So we want him to keep going as long as he’s NOT in “null” land ( hare !== null)
Now let’s put in the shell of our “while” loop. We’ll combine our two conditions with an “&&” logical operator.
class Node {
constructor(val) {
this.val = val
this.next = next
}
}
class SinglyLinkedList {
constructor() {
this.length = 0
this.head = null
this.tail = null
}
findMiddleElement() {
let tortoise = this.head
let hare = this.head
if(!this.head) {
return undefined
}
while ( hare !== null && hare.next !== null) {
}
}
}
The next part is easy. In the body of the “while” statement we want to let our heroes go! We’ll use “dot next” (.next) to tell each hero to move to the next node. That means the tortoise can go (.next), but the hare has to go twice as fast (.next.next). Like this:
class Node {
constructor(val) {
this.val = val
this.next = next
}
}
class SinglyLinkedList {
constructor() {
this.length = 0
this.head = null
this.tail = null
}
findMiddleElement() {
let tortoise = this.head
let hare = this.head
if(!this.head) {
return undefined
}
while ( hare !== null && hare.next !== null) {
tortoise = tortoise.next
hare = hare.next.next
}
}
}
And lastly, we’ll retrieve our prize. Once the while loop has run its course, our hare will be sitting at the end of the linked list while our tortoise will be at the median point. Let’s get tortoise’s data value in our final return statement to complete the algorithm:
class Node {
constructor(val) {
this.val = val
this.next = next
}
}
class SinglyLinkedList {
constructor() {
this.length = 0
this.head = null
this.tail = null
}
findMiddleElement() {
let tortoise = this.head
let hare = this.head
if(!this.head) {
return undefined
}
while ( hare !== null && hare.next !== null) {
tortoise = tortoise.next
hare = hare.next.next
}
return hare.val
}
}
This tortoise and the hare approach is useful in other kinds of problems, too. Keep this approach on your back burner whenever you’re looking at linked lists or any kind of cycles where you’re trying to find the end, middle point or where something intersects with something else.
Happy interviewing and best wishes!
Top comments (0)