Find the second last node of a linked list in single traversal
Last Updated :
11 Jan, 2023
Given a linked list. The task is to find the second last node of the linked list using a single traversal only.
Examples:
Input : List = 1 -> 2 -> 3 -> 4 -> 5 -> NULL
Output : 4
Input : List = 2 -> 4 -> 6 -> 8 -> 33 -> 67 -> NULL
Output : 33
The idea is to traverse the linked list following the below approach:
- If the list is empty or contains less than 2 elements, return false.
- Otherwise, check if the current node is the second last node of the linked list or not. That is, if (current_node->next-next == NULL ) then the current node is the second last node.
- If the current node is the second last node, print the node otherwise move to the next node.
- Repeat the above two steps until the second last node is reached.
Below is the implementation of the above approach:
C++
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node* next;
};
int findSecondLastNode(struct Node* head)
{
struct Node* temp = head;
if (temp == NULL || temp->next == NULL)
return -1;
while (temp != NULL) {
if (temp->next->next == NULL)
return temp->data;
temp = temp->next;
}
}
void push(struct Node** head_ref, int new_data)
{
Node* new_node = new Node;
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
int main()
{
struct Node* head = NULL;
push(&head, 12);
push(&head, 29);
push(&head, 11);
push(&head, 23);
push(&head, 8);
cout << findSecondLastNode(head);
return 0;
}
|
Java
class Node
{
int data;
Node next;
Node(int d)
{
this.data = d;
this.next = null;
}
}
class LinkedList
{
Node start;
LinkedList()
{
start = null;
}
public void push(int data)
{
if(this.start == null)
{
Node temp = new Node(data);
this.start = temp;
}
else
{
Node temp = new Node(data);
temp.next = this.start;
this.start = temp;
}
}
public int findSecondLastNode(Node ptr)
{
Node temp = ptr;
if(temp == null || temp.next == null)
return -1;
while(temp.next.next != null)
{
temp = temp.next;
}
return temp.data;
}
public static void main(String[] args)
{
LinkedList ll = new LinkedList();
ll.push(12);
ll.push(29);
ll.push(11);
ll.push(23);
ll.push(8);
System.out.println(ll.findSecondLastNode(ll.start));
}
}
|
Python3
import math
class Node:
def __init__(self, data):
self.data = data
self.next = None
def findSecondLastNode(head):
temp = head
if (temp == None or temp.next == None):
return -1
while (temp != None):
if (temp.next.next == None):
return temp.data
temp = temp.next
def push(head, new_data):
new_node = Node(new_data)
new_node.next = head
head = new_node
return head
if __name__ == '__main__':
head = None
head = push(head, 12)
head = push(head, 29)
head = push(head, 11)
head = push(head, 23)
head = push(head, 8)
print(findSecondLastNode(head))
|
C#
using System;
public class Node
{
public int data;
public Node next;
public Node(int d)
{
this.data = d;
this.next = null;
}
}
public class LinkedList
{
Node start;
LinkedList()
{
start = null;
}
public void push(int data)
{
if(this.start == null)
{
Node temp = new Node(data);
this.start = temp;
}
else
{
Node temp = new Node(data);
temp.next = this.start;
this.start = temp;
}
}
public int findSecondLastNode(Node ptr)
{
Node temp = ptr;
if(temp == null || temp.next == null)
return -1;
while(temp.next.next != null)
{
temp = temp.next;
}
return temp.data;
}
public static void Main()
{
LinkedList ll = new LinkedList();
ll.push(12);
ll.push(29);
ll.push(11);
ll.push(23);
ll.push(8);
Console.WriteLine(ll.findSecondLastNode(ll.start));
}
}
|
Javascript
<script>
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
function findSecondLastNode( ptr)
{
var temp = head ;
if (temp == null || temp.next == null)
return -1 ;
while (temp != null)
{
if (temp.next.next == null)
return temp.data;
temp = temp.next;
}
}
function push( data)
{
var new_node = new Node(data) ;
new_node.next = head ;
head = new_node ;
return head ;
}
var head = null ;
head = push(12);
head = push(29);
head = push(11);
head = push(23);
head = push(8);
document.write(findSecondLastNode(head));
</script>
|
Time complexity: O(n), where N is the number of nodes in the LinkedList.
Auxiliary Space: O(1), as constant space is used.