Two-Pointer Linked List Techniques

I am working on the Two-Pointer Linked List Techniques for the Computer Science track and have a question about the runner solution code. On the last if statement, if the current node is None it sets current back to the head node. Doesn’t this just mean it’s reached the end of the list? I don’t understand what is going on here in the last piece of this method

Link to class

https://www.codecademy.com/paths/computer-science/tracks/cspath-cs-102/modules/linked-lists/articles/two-pointer-linked-list-techniques-python

def nth_last_node(linked_list, n): current = None tail_seeker = linked_list.head_node count = 1 while tail_seeker: tail_seeker = tail_seeker.get_next_node() count += 1 if count >= n + 1: if current is None: current = linked_list.head_node else: current = current.get_next_node() return current
2 Likes

Hi,

It bares mention that the goal is to get the nth element of the linked list counting in reverse order, and that n is not referring to the list length, but to the position from the end that is our target (this confused me when first reading the algorithm, as I would use n for the entire size personally).

So in a nutshell the condition if count >= n+1 really means “have we passed the boundary length of the target?” Because then if so, the remaining n elements from the list are going to shift the pointer to its correct location. The graphic provided in that lesson is very good.

Proof:
Let’s say we have a list size M (ugh, lol), then then nth node from the end is the M-n+1th element. (The trivial case being the first node from the end, the tail, is the M-1+1=Mth element). Once we cross over n steps from our first element (n+1), by definition we have M-n+1 steps left to move out of bounds. So if we set our goal pointer to start moving from the head there, we will arrive at our M-n+1th position, as desired.

A graphical example:

Let M = 8 and n=3
3rd to last item from 
1 2 3 4 5 6 7 8
A B C D E F G H
          T          (T for target)
means we have to reach the (n+1) threshold which is 4.

Once we are here, we have 8-3=5 steps left (to be out), 
(when the seeker is on 3, we have M-n+1=8-3+1=6 steps left) 
1 2 3 4 5 6 7 8
A B C D E F G H
      ^
if we now set a target pointer to head

1 2 3 4 5 6 7 8
A B C D E F G H
      ^
*

by the time we go out of bounds we will have our desired
target, 6

1 2 3 4 5 6 7 8
A B C D E F G H
                ^
          *
Victory!
1 Like

Consistently inconsistent notation, don’t you just love it :rofl:

1 Like

To be fair I think this is representative of the feeling of getting slightly oddly worded questions in interviews.

Silver lining? Maybe copper lining at best.

1 Like

I probably shouldn’t say anything, I have in the past had to deal with both astronomy and magnetism which basically dumps engineers, physicists, mathematicians and astronomers in the same box where none of them can agree and it all gets a bit “Life of Brian” :neutral_face:.

1 Like