How to find the second last element of SLList

Structure of the SLList

Let’s understand the basic structure of a SLList. In a SLList (singly-linked list), each element, known as a Node, contains a value and a pointer to the next node. The last node’s pointer is typically set to NULL to indicate the end of the list.

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

Traverse the SLList

To find the second last element, we must traverse the list until we reach the node just before the last node. Therefore, we must maintain two pointers, one pointing to the current node and another to the previous node. We can identify the second last element efficiently by updating these pointers as we traverse the list.

Here’s an example of a SLList with five nodes:

#include <iostream>
using namespace std;
struct Node {
    int value;
    Node* next;
};
void printLinkedList(Node* head) {
    Node* current = head;
    while (current != nullptr) {
        cout << current->value << " -> ";
        current = current->next;
    }
    cout << "NULL" << endl;
}
int findSecondLastElement(Node* head) {
    if (head == nullptr || head->next == nullptr) {
        cout << "List is empty or contains only one element.";
        return -1; // Handle edge cases
    }
    Node* current = head;
    Node* previous = nullptr;
    while (current->next != nullptr) {
        previous = current;
        current = current->next;
    }
    return previous->value;
}
int main() {
    // Example usage
    Node* head = new Node{ 10, nullptr };
    head->next = new Node{ 20, nullptr };
    head->next->next = new Node{ 30, nullptr };
    head->next->next->next = new Node{ 40, nullptr };
    head->next->next->next->next = new Node{ 50, nullptr };
    cout << "Linked List: ";
    printLinkedList(head);
    int secondLast = findSecondLastElement(head);
    cout << "The second last element is: " << secondLast << endl;
    // Cleanup (deallocate memory)
    Node* current = head;
    while (current != nullptr) {
        Node* temp = current;
        current = current->next;
        delete temp;
    }
    return 0;
}

Explanation

Line 8: We implement the printLinkedList() function that takes a pointer to the head of the linked list as a Node* head parameter. The purpose of this function is to traverse the linked list and print the values of each node.
Line 9: We initialize a Node variable current with the head pointer.
Lines 11–14: We traverse the list using the while loop and print the value of each node by updating the current pointer current = current->next.
Line 16: Finally, when the loop exits, it prints "NULL" to signify the end of the list.
Line 19: We implement the findSecondLastElement()function that takes a pointer to theheadof the linked list as a parameterNode* head`.
Line 20: We check the list to see if it is empty or contains one element by examining head and head->next.
Lines 25–26: We initialize two node pointers, current with head and previous with nullptr.
Lines 28–30: We traverse the list using the while loop until the current pointer reaches the last node. We update the previous pointer to point to the current node previous = current and advance the current pointer to the next node current = current->next.
Line 33: We return the value of the second last node, return previous->value.

Inside the main() function, the nodes with values 10, 20, 30, 40, and 50 are created and added to the linked list. Each node is assigned a value, and its next pointer is initially set to nullptr. After printing the second last element, it deallocates the memory occupied by the nodes in the linked list. It iterates through the list, deallocates each node using the delete keyword, and updates the current pointer to the next node until it reaches the end of the list.

How to find the second last element of SLList

Structure of the SLList

Traverse the SLList

Algorithm

Code

Explanation