Program for Nth node from the end of a Linked List | DSA in C++ - Software Development PDF Download

Introduction

In this article, we will explore a common problem in data structures and algorithms: finding the Nth node from the end of a linked list. We will provide a step-by-step explanation along with simple code examples in C++ to help beginners understand the concept. Additionally, we will include sample problems with solutions to further enhance your understanding.

What is a Linked List?

Problem Statement: Finding the Nth Node from the End

Given a linked list, we are tasked with finding the Nth node from the end of the list. For example, if we have a linked list: 1 -> 2 -> 3 -> 4 -> 5, and we want to find the 2nd node from the end, the expected output should be 4.

Approach 1: Counting Nodes

One straightforward approach to solve this problem is by counting the total number of nodes in the linked list. Once we know the total count, we can easily determine the position of the Nth node from the end.

Algorithm:

• Traverse the entire linked list and count the number of nodes.
• Subtract the desired position (N) from the total count to get the position from the beginning.
• Traverse the list again, stopping at the desired position.

Code Example:

int getCount(ListNode* head) {

    int count = 0;

    ListNode* current = head;

    while (current != nullptr) {

        count++;

        current = current->next;

    }

    return count;

}

ListNode* findNthNodeFromEnd(ListNode* head, int N) {

    int count = getCount(head);

    int positionFromStart = count - N;

    ListNode* current = head;

    for (int i = 0; i < positionFromStart; i++) {

        current = current->next;

    }

    return current;

}

Approach 2: Two Pointers (Optimized Approach)

The counting approach mentioned above requires traversing the linked list twice. We can optimize it by using two pointers: a fast pointer and a slow pointer.

Algorithm:

• Initialize both pointers, fast and slow, to point to the head of the linked list.
• Move the fast pointer N positions ahead.
• Move both pointers simultaneously until the fast pointer reaches the end of the list.
• The slow pointer will then be pointing to the Nth node from the end.

Code Examples

ListNode* findNthNodeFromEnd(ListNode* head, int N) {

    ListNode* fast = head;

    ListNode* slow = head;

    // Move the fast pointer N positions ahead

    for (int i = 0; i < N; i++) {

        if (fast == nullptr) {

            // Handle the case when N is greater than the length of the list

            return nullptr;

        }

        fast = fast->next;

    }

    // Move both pointers simultaneously

    while (fast != nullptr) {

        fast = fast->next;

        slow = slow->next;

    }

    return slow;

}

Code Examples

Now, let's see how the code works in different scenarios.

Example 1: Using Approach 1

int main() {

    ListNode* head = new ListNode(1);

    head->next = new ListNode(2);

    head->next->next = new ListNode(3);

    head->next->next->next = new ListNode(4);

    head->next->next->next->next = new ListNode(5);

    int N = 2;

    ListNode* nthNode = findNthNodeFromEnd(head, N);

    if (nthNode != nullptr) {

        cout << "Nth node from the end: " << nthNode->val << endl;

    } else {

        cout << "Invalid position." << endl;

    }

    return 0;

}

Output:

Nth node from the end: 4

Example 2: Using Approach 2

int main() {

    ListNode* head = new ListNode(1);

    head->next = new ListNode(2);

    head->next->next = new ListNode(3);

    head->next->next->next = new ListNode(4);

    head->next->next->next->next = new ListNode(5);

    int N = 3;

    ListNode* nthNode = findNthNodeFromEnd(head, N);

    if (nthNode != nullptr) {

        cout << "Nth node from the end: " << nthNode->val << endl;

    } else {

        cout << "Invalid position." << endl;

    }

    return 0;

}

Output:

Nth node from the end: 3

Sample Problems

Here are a few additional problems related to finding the Nth node from the end of a linked list:

Problem 1: Given a linked list, determine if it contains a cycle. If it does, find the Nth node from where the cycle starts.

This problem can be solved using Floyd's cycle-finding algorithm.

Problem 2: Find the middle node of a linked list.

Use the two-pointer technique, where one pointer moves at half the speed of the other.

Conclusion

In this article, we covered the problem of finding the Nth node from the end of a linked list. We discussed two approaches, one based on counting nodes and another optimized approach using two pointers. Both approaches provide efficient solutions to the problem. By understanding these concepts and practicing the provided code examples, you should now have a solid foundation for solving similar linked list problems.