Two Pointer Linked List Techniques Python

Problems with a normally connected list can be solved by repeating with two pointers. Two Pointers Moving in Parallel

Consider the following problem:

Create a way to return the ninth last element of the same linked list.

To do this, you need some way to know how far you are from the end of the list.

If you wish, you can try your hand at the problem directly, or we can follow some of the approaches below.

Approaches

One thing that comes to mind first is to use this list to store the list representation attached to the list. , And then get the ninth to last element of this list.

The code for this view will look like the following:

def list_nth_last(linked_list, n): linked_list_as_list = [] current_node = linked_list.head while current_node: linked_list_as_list.append(current_node) current_node = current_node.get_next_node() return linked_list_as_list[len(linked_list_as_list) – n]

Instead of creating a complete parallel list, we can solve this problem by using two pointers at different positions in the list but at the same rate.

The side code for this view will look like the following:

nth last pointer = None tail pointer = linked list head count = 0 while tail pointer exists move tail pointer forward if count >= n set nth last pointer to head if it's still None or move it forward increment count return nth last pointer Implementation

Leave a Comment

Your email address will not be published. Required fields are marked *