Find the Nth Node from the End of a Linked List in C

This program demonstrates how to find the nth node from the end of a linked list using the C programming language. It employs the two-pointer technique to efficiently determine the target node without needing to calculate the total length of the list first.

Program Explanation

The program is structured around a single linked list node structure and includes functions for adding nodes, finding the nth node from the end, and displaying the list. The primary logic involves using two pointers, both starting at the head of the list, with one pointer advancing n steps ahead of the other.

• struct Node: Represents each node in the linked list, containing an integer data and a pointer to the next node.
• appendNode: Adds a new node to the end of the list.
• findNthFromEnd: Identifies the nth node from the end using the two-pointer approach.
• printList: Displays the content of the linked list.

Source Code

#include <stdio.h>
#include <stdlib.h>

struct Node {
    int data;
    struct Node* next;
};

// Function to add a node at the end of the linked list
void appendNode(struct Node** head_ref, int new_data) {
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    struct Node* last = *head_ref;  // used to traverse till the last node

    new_node->data = new_data;  // inserting the data
    new_node->next = NULL;     // next of new node will be NULL as it's going to be the last node

    // If the Linked List is empty, then make the new node as head
    if (*head_ref == NULL) {
        *head_ref = new_node;
        return;
    }

    // Else traverse till the last node
    while (last->next != NULL) {
        last = last->next;
    }

    // Change the next of last node
    last->next = new_node;
}

// Function to find the nth node from the end of a linked list
struct Node* findNthFromEnd(struct Node* head, int n) {
    struct Node *main_ptr = head, *ref_ptr = head;

    int count = 0;
    if (head != NULL) {
        while (count < n) {
            if (ref_ptr == NULL) {
                printf("%d is greater than the number of nodes in list\\n", n);
                return NULL;
            }
            ref_ptr = ref_ptr->next;
            count++;
        }

        while (ref_ptr != NULL) {
            main_ptr = main_ptr->next;
            ref_ptr = ref_ptr->next;
        }
        return main_ptr;
    }
    return NULL; // if the list is empty
}

// Function to print nodes in a given linked list
void printList(struct Node* node) {
    while (node != NULL) {
        printf("%d ", node->data);
        node = node->next;
    }
    printf("\\n");
}

int main() {
    struct Node* head = NULL;
    struct Node* nthNode;

    // Append nodes to the list
    appendNode(&head, 10);
    appendNode(&head, 20);
    appendNode(&head, 30);
    appendNode(&head, 40);
    appendNode(&head, 50);

    printf("Given linked list:\\n");
    printList(head);

    int n = 3;
    nthNode = findNthFromEnd(head, n);
    if (nthNode != NULL) {
        printf("The %dth node from the end of linked list is %d\\n", n, nthNode->data);
    }

    return 0;
}
        

Conclusion

The provided C program efficiently finds the nth node from the end of a linked list using a two-pointer approach. This method is particularly useful as it eliminates the need for a preliminary pass to determine the list’s length, thereby optimizing the operation to O(n) time complexity.