Skip to main content

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

Find the second last node of a linked list

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):
    if head is NULL:
        Display "Empty linked list"
    else if head.next is NULL:
        Display "Only one node in this linked list"
    else:
        Initialize prevNode to NULL
        Initialize currentNode to head
        
        While currentNode.next is not NULL:
            prevNode = currentNode
            currentNode = currentNode.next
        
        Display "Second last element is:", prevNode.data

Algorithm Explanation

  1. If the linked list is empty, display "Empty linked list."
  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.

Code Solution

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.

New Comment