Welcome back to interview prep. In this series, we are examining common technical interview questions in the realm of data structures and algorithms.
If you’ve never heard of singly linked lists before, then you should read my basic article on linked lists first. Otherwise, let’s push on!
So here’s our problem for today: Given a singly linked list, remove the nth node from the end of the list.
Let’s understand the question.
We’re given the linked list below as well as the integer “4”
As we can see above, our linked list consists of node containing integers from 0 to 9. The head node (H) is at 0 and the tail node (T) is at 9.
Now let’s remove the nth node from the list. We were given n = 4, so we’ll remove the 4th node from the end.
If we count the nodes backwards beginning from the tail node, or “9”, the 4th node from the end is “6”. Let’s remove it. Now our node will look like the list in blue below:
How Do We Do This?
First, let’s understand conceptually how we approach this question.
Our first problem is finding the 4th node from the end of the list. In our code, we cannot traverse a singly linked list backwards. The only way we may traverse our list is starting at the head and moving in one direction until we reach “null” after the tail.
Think of a singly linked list as a one-way street.
But not to worry, we have a plan!
First, let’s set two pointers at the head of our list. We’ll call those two pointers “first” (F) and “second” (S)
Now let’s advance our “second” pointer “n” number of places. Our “n” is 4, so let’s advance “S” by 4 places:
So now our pointers are 4 places apart from each other.
Next step is to start advancing each pointer by 1. Let’s do this together in our heads:
Advance S to 5; advance F to 1
Advance S to 6; advance F to 2
Advance S to 7; advance F to 3
and so on….
We’ll have to stop advancing pointers when S gets to null. At that moment, our points will look like this:
Look at that! Our “S” pointer ended at “null” while our
“F” pointer ended at “6”. We notice that “6” is the 4th node from the end of the list--exactly the node we needed to find!
Now that we’ve found the node we need to remove, we’ll get rid of it by resetting the node before it, “5”, to point at “7”.
Let’s Code It Up!
Now you have a conceptual understanding of how we’ll solve this algorithm. Let’s code it up!
Remember, the only things we can “see” of a linked list are the head, and tail. Also, we can only traverse the linked list starting at the head and moving towards the tail.
In our function, removeNthNodeFromEnd, we’ll use “head” and “n” as parameters.
const removeNthNodeFromEnd = ( head, n ) => {
}
Now let’s set our first pointer, variable “first”, and our
second pointer, variable “second”, to “head”.
We’ll also need a counter variable( set counter to “1”) to keep track of the number of places we traverse in the list:
const removeNthNodeFromEnd = ( head, n ) => {
let first = head
let second = head
let counter = 1
}
To get the “second” pointer to traverse 4 places on our list, we’ll use a “while” loop
const removeNthNodeFromEnd = ( head, n ) => {
let first = head
let second = head
let counter = 1
while( counter <= n ) {
second = second.next
counter ++
}
}
We’re getting there! We now have “second” set four places ahead of “first”.
Next step is to start both pointers traversing the list--each moving one node at a time in step with each other. When “second” finally gets to the end of the list and gets to “null”, we want to stop the traversing of “first”.
But wait! We have a little edge case to deal with. What if, after advancing “second” by “n” places, “second” points to “null”? It would look like this:
We see that “S” is at “null” and the node we need to remove at “F” is actually the head node. We cannot just remove the head node like we could any middle node. If we remove the head node, we must reset the head node to the next node. In our example, the new head node would be “1”. Let’s take care of that edge case:
const removeNthNodeFromEnd = ( head, n ) => {
let first = head
let second = head
let counter = 1
while( counter <= n ) {
second = second.next
counter ++
}
//edge case if second points to “null”:
if ( second === null ) {
// update value of the head node
head.value = head.next value
//update the pointer of the head node:
head.next = head.next.next
// and we’re done. Let’s just exit the function
return head
}
}
Now that the edge case is out of the way, let’s have each pointer traverse the list. However, we want to stop the traversal when “second” gets to the last node before “null”.
That means “first” will land on the node before the one we really want to eliminate.
Our pointers will look like this:
Why do we do this? Well, think of the links between the nodes as little tied knots in a string. If we really traversed to the “6”, the one we want to eliminate, and then “untied” its knot to “7” we would have lost the reference to the “7”. Think of the “7” then being unlinked to the rest of the list, it would just “float” away.
The way we need to get rid of the “6” is via it’s immediate previous neighbor -- the “5”
What we’ll do now that “first” is pointing at “5” is we’ll “retie” the 5’s “next” knot to 7. Visualize this. You’ll see how nothing gets untied in the process. Once we “tie” the 5 to the 7, now we can safely untie the 6 from the 7. The six can then just float off into computer infinity.
Let’s do it. I’ll write the code to advance both pointers so long as “second” IS NOT null:
const removeNthNodeFromEnd = ( head, n ) => {
let first = head
let second = head
let counter = 1
while( counter <= n ) {
second = second.next
counter ++
}
//edge case if second points to “null”:
if ( second === null ) {
// update value of the head node
head.value = head.next value
//update the pointer of the head node:
head.next = head.next.next
// and we’re done. Let’s just exit the function
return head
}
// now we advance each pointer. Let’s
// keep going so long as second IS NOT null
while ( second. next !== null ) {
second = second.next
first = first. next
}
}
We’re down to our last line of code now!
We just have to do that “retying” explained above. So we got our first pointer at 5, the node before the 6--the node we want to get rid of. We know we just have to “retie” the 5 to the node after 6, or 7.
How do we “re-tie” our 5 to the 7?
We just do:
first.next = first.next.next
On the right side of the expression, “first” is set to “5”. That means first.next would be “6” and first.next.next is “7”. I’m saying, “Set 7 to be the next node after “first” or “5”.
See the final code below
const removeNthNodeFromEnd = ( head, n ) => {
let first = head
let second = head
let counter = 1
while( counter <= n ) {
second = second.next
counter ++
}
//edge case if second points to “null”:
if ( second === null ) {
// update value of the head node
head.value = head.next value
//update the pointer of the head node:
head.next = head.next.next
// and we’re done. Let’s just exit the function
return head
}
// now we advance each pointer. Let’s
// keep going so long as second IS NOT null
while ( second. next !== null ) {
second = second.next
first = first. next
}
first.next = first.next.next
// does the interviewer want us to return something?
}
I would ask the interviewer what, if anything, they want us to return. Maybe the head? Maybe “n”? Maybe just the string “I did it! Yay!”
Space and Time Complexity
We are just traversing a list one time. There is no nested looping, so we have O(n) time complexity
We are not creating any new data structures with our algorithm. All our operations are done in place on the one list so our space complexity is a cool O(1)
And there you have it. A fun, relatively easy algorithm to remove a node “n” places from the end of a singly linked list.
Happy coding and best wishes with your interviews!
Top comments (0)