Discover data structures and algorithms using Python. Gain insights into solving real-world problems and typical interview questions with detailed reviews, explanations, and hands-on coding exercises.

Data structures and algorithms are among the most fundamental concepts of Computer Science. Whether it’s real-world problems you’re trying to solve or the typical coding question asked in an interview, almost every problem requires you to demonstrate a deep understanding of data structures and algorithms. 

This course is a detailed review of some of the most common data structures and algorithms that you’ll see in interviews and your everyday work. With implementation details, thorough explanations, and hands-on coding exercises, you’ll quickly gain the confidence you need to solve any problem, no matter the situation.

Data Structures and Algorithms in Python

In this lesson, we are going to find how to get the *Nth-to -Last Node* from a linked list. 
First of all, we'll clarify what we mean by *Nth-to -Last Node* in the illustration below:

As you can see from the illustration above, if `N` equals `2`, we want to get the second to last node from the linked list. 

We will be using two solutions to solve this problem. 

# Solution 1 

We'll break down this solution in two simple steps:

1. Calculate the length of the linked list.
2. Count down from the total length until `n` is reached. 

For example, if we have a linked list of length four, then we'll begin from the head node and decrement the calculated length of the linked list by one as we traverse each node in the linked list. We'll only stop on the node when our count becomes equal to `n`.
 
## Implementation 
Let's try implementing this solution in Python:

def print_nth_from_last(self, n):
  total_len = self.len_iterative()
  
  cur = self.head 
  while cur:
    if total_len == n:
      print(cur.data)
      return cur.data
    total_len -= 1
    cur = cur.next
  if cur is None:
    return  

## Explanation
The method `print_nth_from_last` only takes in `n` as an input parameter. You are already familiar with how to calculate the length of a linked list from a previous lesson. We'll use the class method `self.len_iterative()` that we have implemented before to calculate the length of the linked list and store it in the variable named `total_len` on **line 2**.

So far, we have completed step 1 of solution 1. Let's move on to the second step. `cur` is initialized to `self.head` on **line 4**. Next, we have a `while` loop on **line 5** which will traverse the entire linked list or stop after traversing n nodes. In the body of the `while` loop, we check if `total_len` equals `n` which is our primary goal for this method. If `total_len` equals `n`, we print the `data` of the current node (`cur`) and return the data of the current node from the method. Otherwise, we decrement `1` from `total_len` on **line 9** and update `cur` to the next node on **line 10** to traverse the linked list. 

If, however, we reach the end of the linked list but `total_len` never becomes equal to `n`, then we handle this on **lines 11-12**. In this case, we check if `cur` is `None` and we return from the method. 

# Solution 2

That was all about Solution 1. Let's proceed with Solution 2, which can be described as follows:

There will be a total of two pointers `p` and `q`:
* `p` will point to the head node. 
* `q` will point `n` nodes beyond head node. 

Next, we'll move these pointers along with the linked list one node at a time. When `q` will reach `None`, we'll check where `p` is pointing, as that is the node we want. 
## Implementation
Let's make it clearer by implementing it in Python:

In this lesson, we will learn how to get the Nth-to-Last Node from a given linked list. 

Introduction

Stack

Singly Linked Lists

Circular Linked Lists

Doubly Linked Lists

Arrays

Binary Trees

Binary Search Trees

Binary Search

Recursion

String Processing

Nth-to-Last Node

Solution 1 #