Data Structures in Python: Singly Linked Lists -- Nth-to-Last Node

In this video, we investigate how to find the nth-to-last node in a singly linked list.

The software written in this video is available at:

The other video in this series mentioned is how one can calculate the length of a singly linked list:

Do you like the development environment I'm using in this video? It's a customized version of vim that's enhanced for Python development. If you want to see how I set up my vim, I have a series on this here:

If you've found this video helpful and want to stay up-to-date with the latest videos posted on this channel, please subscribe:

[erickmwazonga]

These are by far the best Data Structures tutorials I have ever encountered. Thanks

[ksuniljoshi]

Thanks for the wonderful stuff you have put in, please go ahead and make videos on other data structures(graphs, hash tables, queue) if possible also on dynamic and greedy programming, as I see your explanation is really good.

[areebasif]

You deserve at least million views. The way you explain things, I haven't seen more lucid explanations. Go ahead buddy with more videos and we'll keep sharing and subscribing.

[heidik]

Hey! Just a quick question for method one why did you both return and print the value?

[heidik]

one other question, no pressure if you can't answer... but! you also placed a return statement... with nothing beside it. would this make this result invisible vs. none?

[madhu]

Hi, Can anyone please tell me, how to pop second element from stack? Means top element in stack remains same, the element below top is removed on pop(). I really need help with this.

[yunalee]

Thank you for this tutorial and it is the most clear one I found. I am wondering what if we want to return to the linked list without nth node rather than nth node itself from two pointer method? Do you need to use delete function to delete it? I cannot figure out a way to do it without calling delete function? Do you have any advice?

[VinayAdithya_googler_at_heart]

Man, you are a god sent! I had such a mental blockage about data structure and your videos have dusted them off.


However, I noticed this error in the second (two pointers )method.
When n = max length, the code spits out q = None value.
changing the condition " if not q:" to "if not q and count !=n: " fixes it .

[micejp]

Hello, Mr. Lucid..

Thank you for your nice videos and I can tell you your videos help people who want to learn programming.. By the way, I found that method 2 has a bug. If I tried to found 4th element in list which have four elements, it would show the error message of assigning number greater than list length. But there are 4 elements and method 1 works well without any errors..

[yogitasinkar]

Hey, It's been amazing following your data structures series so far. I have a quick question though. Is there any difference writing: - if not q and if q is None

[josedanielgallegos]

Love your videos man. Thank you for all of them

In the second while loop:

while p and q:

I think you don't need p, only checking if q is not empty will be necessary. It will be:

while q:
do the rest.

What do you think?

[deojeetsarkar]

2nd method: using pointers O(n) from 7:07

[kittipobkomjaturut]

Can you please explain why we need method 2? What are pros and cons of the two ?

[ANAKIN]

Thank you for amazing content and your tutorials are great!!
I used following approach for this problem:-

def nth_to_last(self, n):
cur=self.head
count=0
while cur and
count+=1
cur=cur.next
print(cur.data)

This code is giving correct output.
Can you tell if it is fine or any mistake.

[mulhamjarjanazi]

I solved it using the following code:


def Nth_to_last(self, N):
current_node = self.head
nodes = []

while current_node:
nodes.append(current_node)
current_node = current_node.next

return nodes[-1-N]


what do you think about it?

[anuraagsaraswat]

def length(self):
cur = self.head
count=0
while cur:
cur = cur.next
count += 1
return count

def nth_to_last(self, n):
data = list()
cur = self.head
while cur:
for i in range(self.length()):
data.append(cur.data)
cur = cur.next
return data[-n]

[prachinainawa]

You should have used a pointer to the last node, in all the vid of linked list.

[shubhamjaiswal]

thanks for the nice tutorial @LucidProgramming.
This is how I did.
def n_to_last(self, n):
count = 0
curr = self.head
while curr:
count = count + 1
curr = curr.next
print("the number of data in the LinkedList is:-", count)
reverse_counter = count
curr = self.head
if n in range(1, reverse_counter + 1):
while curr:
if reverse_counter is n:
position_data = curr.data
reverse_counter = reverse_counter - 1
curr = curr.next
print("The data you are looking is:-", position_data)

else:
print("Sorry, the given number is out of bound.")


Sir, I couldn't understand the second method please elaborate it.

[IntrestingRandomFacts]

Nicely explained
The 2nd code won't work for first(max length) of node.
Ex : 1-2-3-4-5-6 if you want to check for 6th item. It will say as number bigger then length of list


Add below lines before checking if "p" is None
if not cur and count == n:
return p.data

[pawanmandal]

def sec_lst_ele(self):
cur = self.head
pre = None
sec = None
while cur.next:
pre = cur
sec = pre.value
cur = cur.next
return sec