Algorithms

Find the nth node from the end of a singly linked list ?

In this article, we will discuss an algorithm to find the nth node from the end of a singly linked list. First, let’s discuss what is singly liked list.

Singly Linked List

It is a linked list, we can traverse only forward direction. We can’t move to backwards. That means, in a singly linked list, each node in the list has the content and a pointer to the next node in the list. It does not store any pointer to the previous node. To store a single linked list, only the pointer to the first node in that list must be stored. The last node in a single linked list points to nothing.

The nth node from the end of a singly linked list

There are many solutions to this problem are available online specifically in GeeksforGeeks. Let’s discuss one of the solutions to this problem.

Step 1: First, let’s take two pointers to suppose pointer1 and pointer2.

Step 2: Intially initialize these two pointers with the head of the linked list.

pointer1=head;
pointer2=head;

Step 3: Now fix the pointer1 and let’s pointer2 till the nth node from the head of the singly linked list.

while(n > 0){
    pointer2 = pointer2->next;
     n--;
}

Step 4: If pointer2 is the last node of the singly linked then pointer1 is the nth node from the end.

Step 5: If pointer2 is not the last node of the singly liked list then let’s start moving forward pointer1 till pointer2 will reach to the last node of this singly linked list.

while(pointer2->next != null){
    pointer2 = pointer2->next;
    pointer1 = pointer1->next;
}

Step 6: Finally, we found pointer1 as the nth node from the end of the singly linked list.

Code

//Pseudo code


function(head,n){
    pointer1=head
    pointer2=head

    while(n--){
        pointer2=pointer2.next
    }
    //pointer2 reached nth node
    while(pointer2.next is not null){
        pointer2=pointer2.next
        pointer1=pointer1.next
    }

    return pointer1
}

Hope, you have understood this solution for the above find the nth node from the end of a singly linked list. Please share other solutions if you have. :).

Happy learning with us!!!.

Next
Dinesh Rajput

Dinesh Rajput is the chief editor of a website Dineshonjava, a technical blog dedicated to the Spring and Java technologies. It has a series of articles related to Java technologies. Dinesh has been a Spring enthusiast since 2008 and is a Pivotal Certified Spring Professional, an author of a book Spring 5 Design Pattern, and a blogger. He has more than 10 years of experience with different aspects of Spring and Java design and development. His core expertise lies in the latest version of Spring Framework, Spring Boot, Spring Security, creating REST APIs, Microservice Architecture, Reactive Pattern, Spring AOP, Design Patterns, Struts, Hibernate, Web Services, Spring Batch, Cassandra, MongoDB, and Web Application Design and Architecture. He is currently working as a technology manager at a leading product and web development company. He worked as a developer and tech lead at the Bennett, Coleman & Co. Ltd and was the first developer in his previous company, Paytm. Dinesh is passionate about the latest Java technologies and loves to write technical blogs related to it. He is a very active member of the Java and Spring community on different forums. When it comes to the Spring Framework and Java, Dinesh tops the list!

Share
Published by
Dinesh Rajput

Recent Posts

Strategy Design Patterns using Lambda

Strategy Design Patterns We can easily create a strategy design pattern using lambda. To implement…

2 years ago

Decorator Pattern using Lambda

Decorator Pattern A decorator pattern allows a user to add new functionality to an existing…

2 years ago

Delegating pattern using lambda

Delegating pattern In software engineering, the delegation pattern is an object-oriented design pattern that allows…

2 years ago

Spring Vs Django- Know The Difference Between The Two

Technology has emerged a lot in the last decade, and now we have artificial intelligence;…

2 years ago

TOP 20 MongoDB INTERVIEW QUESTIONS 2022

Managing a database is becoming increasingly complex now due to the vast amount of data…

2 years ago

Scheduler @Scheduled Annotation Spring Boot

Overview In this article, we will explore Spring Scheduler how we could use it by…

3 years ago