Posted on by Kalkicode

# Find the second last node of a linked list

The problem addressed in this code involves finding the second last node of a singly linked list. A singly linked list is a linear data structure in which each element is called a node and consists of data and a reference to the next node in the sequence.

## Problem Statement and Description

Given a singly linked list, the task is to write a program that finds and prints the value of the second last node in the list. If the list contains only one node, or if it is empty, appropriate messages are displayed.

## Example

Consider the following singly linked list:

``6 → 3 → 2 → 7 → 1 → 9 → null``

The second last node in this linked list has the value `1`.

## Idea to Solve the Problem

To solve this problem, we can follow these steps:

1. Traverse the linked list while keeping track of two pointers: one for the current node and another for the node before it.
2. When the current node reaches the end of the list, the node before it will be the second last node.

## Standard Pseudocode

Here's a high-level pseudocode representation of the algorithm to find the second last node of a singly linked list:

``````FindSecondLastNode(head):
Display "Only one node in this linked list"
else:
Initialize prevNode to NULL

While currentNode.next is not NULL:
prevNode = currentNode
currentNode = currentNode.next

Display "Second last element is:", prevNode.data``````

## Algorithm Explanation

2. If there's only one node in the linked list, display "Only one node in this linked list."
3. If there are at least two nodes in the linked list:
• Initialize two pointers: `prevNode` and `currentNode`, both starting from the head of the linked list.
• Traverse the linked list until `currentNode.next` is NULL (reaching the end).
• During traversal, keep updating `prevNode` to be the previous node of `currentNode`.
• The node pointed to by `prevNode` will be the second last node.
4. Display the value of the second last node.

## Time Complexity

The time complexity of finding the second last node in a singly linked list using the provided algorithm is O(n), where 'n' is the number of nodes in the linked list. This is because the algorithm needs to traverse the entire list in order to reach the second last node.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post