by Linked List is a data structure used for storing collection of data where successive elements are connected through pointers and the size of linked list can grow or shrink dynamically.
In short, Linked list can be thought as similar to array in which traversal can happen through pointers instead of indexes. Before going ahead have a look into Linked List Basics and Linked List Implementation.
Let’s have a look on basic class definition for Linked List.
class LinkedList
{
public:
int data;
LinkedList* next;
LinkedList (int data);
~LinkedList ();
};
/* Below function will print all nodes in a Linked List */
void print_linked_list (LinkedList* start)
{
if (!start)
{
cout << "Linked list is null, nothing to print" << endl;
return;
}
LinkedList* temp = start;
while (temp)
{
cout << " " << temp -> data;
temp = temp -> next;
}
cout << endl;
}
Nth node from the end of Linked List
There are multiple ways to find Nth node from the end in a linked list.
Sub Optimal Solution
One Sub optimal solution would be to calculate the length of the linked list and using that find the (length – n + 1)th Node in the next traversal of the Linked List. But in this case, we need to traverse the Linked list twice which is very costly in case of very long Linked List. We are not explaining this method here as this is quite trivial.
Optimal Solution
In this case, we will use two pointers fast and slow each apart by n nodes.
Algorithm to find Nth node from the end
- Start traversing the Linked List from the head node.
- Once we reach at nth Node from the start then set slow pointer to head node and fast pointer to nth Node from the head.
- Now keep on increasing both pointers one by one till fast pointer reaches the end of Linked List (encountered the NULL Pointer).
- Node pointed by the slow pointer is the nth Node from the Linked List.
Let’s look into the sample code.
void find_nth_node_from_end (LinkedList* start, int n)
{
LinkedList* fast = start;
LinkedList* slow = start;
int count = 0;
while (fast)
{
++count;
if (count == n)
slow = start;
else if (count > n)
slow = slow -> next;
fast = fast -> next;
}
if (count >= n)
cout << "Node found: " << slow -> data << " nth place: " << n << endl;
else
cout << "Not enough node present, length: " << count << " nth Node searched: " << n << endl;
}
Let’s use these functions in an example main functions to explain the usage of these functions.
Few of the functions used below are explained in Linked List Insert operation, Linked List Delete Operation and Linked List Traverse and Search article . Refer those before moving ahead.
int main()
{
LinkedList* start = NULL;
print_linked_list (start);
insert_at_begining (&start, 3);
insert_after_certain_element (start, 5, 6);
insert_after_certain_element (start, 7, 5);
insert_after_certain_element (start, 9, 8);
insert_after_certain_element (start, 11, 10);
insert_after_certain_element (start, 16, 11);
insert_after_certain_element (start, 2, 9);
insert_after_certain_element (start, 3, 2);
print_linked_list (start);
find_nth_node_from_end (start, 1);
find_nth_node_from_end (start, 3);
find_nth_node_from_end (start, 7);
find_nth_node_from_end (start, 11);
cout << "Deleting Head Node " << endl;
delete_start_node (&start);
print_linked_list (start);
cout << "Deleting Node 11" << endl;
delete_searched_node (&start, 11);
print_linked_list (start);
cout << "Deleting all Nodes" << endl;
delete_all_node (&start);
print_linked_list (start);
}
Let’s analyze the output of this main function.
Linked list is null, nothing to print
Inserting node 5
Searched data not found, hence putting new node at the end
Inserting node 7
Inserting node 9
Searched data not found, hence putting new node at the end
Inserting node 11
Searched data not found, hence putting new node at the end
Inserting node 16
Inserting node 2
Inserting node 3
3 5 7 9 2 3 11 16
Node found: 16 nth place: 1
Node found: 3 nth place: 3
Node found: 5 nth place: 7
Not enough node present, length: 8 nth Node searched: 11
Deleting Head Node
5 7 9 2 3 11 16
Deleting Node 11
Node found, going to delete
5 7 9 2 3 16
Deleting all Nodes
Linked list is null, nothing to print
