Encuentre el penúltimo Node de una lista vinculada en un solo recorrido

Dada una lista enlazada. La tarea es encontrar el penúltimo Node de la lista enlazada utilizando solo un recorrido único.
Ejemplos: 
 

Entrada : Lista = 1 -> 2 -> 3 -> 4 -> 5 -> NULL 
Salida : 4
Entrada : Lista = 2 -> 4 -> 6 -> 8 -> 33 -> 67 -> NULL 
Salida : 33 
 

La idea es recorrer la lista enlazada siguiendo el siguiente enfoque: 
 

1. Si la lista está vacía o contiene menos de 2 elementos, devuelve falso.
2. De lo contrario, compruebe si el Node actual es el penúltimo Node de la lista enlazada o no. Es decir, si (current_node->next-next == NULL ) entonces el Node actual es el penúltimo Node.
3. Si el Node actual es el penúltimo Node, imprima el Node; de lo contrario, muévase al siguiente Node.
4. Repita los dos pasos anteriores hasta llegar al penúltimo Node.

A continuación se muestra la implementación del enfoque anterior: 
 

// C++ program to find the second last node
// of a linked list in single traversal
  
#include <iostream>
using namespace std;
  
// Link list node
struct Node {
    int data;
    struct Node* next;
};
  
// Function to find the second last
// node of the linked list
int findSecondLastNode(struct Node* head)
{
    struct Node* temp = head;
  
    // If the list is empty or contains less
    // than 2 nodes
    if (temp == NULL || temp->next == NULL)
        return -1;
  
    // Traverse the linked list
    while (temp != NULL) {
  
        // Check if the current node  is the
        // second last node or not
        if (temp->next->next == NULL)
            return temp->data;
  
        // If not then move to the next node
        temp = temp->next;
    }
}
  
// Function to push node at head
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;
}
  
// Driver code
int main()
{
    /* Start with the empty list */
    struct Node* head = NULL;
  
    /* Use push() function to construct 
    the below list 8 -> 23 -> 11 -> 29 -> 12 */
    push(&head, 12);
    push(&head, 29);
    push(&head, 11);
    push(&head, 23);
    push(&head, 8);
  
    cout << findSecondLastNode(head);
  
    return 0;
}

// Java program to find the second last node 
// of a linked list in single traversal
  
// Linked list node
class Node
{
    int data;
    Node next;
    Node(int d)
    {
        this.data = d;
        this.next = null;
    }
}
class LinkedList
{
    Node start;
    LinkedList()
    {
        start = null;
    }
      
    // Function to push node at head
    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;
        }
    }
      
    // method to find the second last 
    // node of the linked list 
    public int findSecondLastNode(Node ptr)
    {
        Node temp = ptr;
          
        // If the list is empty or contains less 
        // than 2 nodes
        if(temp == null || temp.next == null)
            return -1;
      
            // This loop stops at second last node
        while(temp.next.next != null)
        {
            temp = temp.next;
        }
        return temp.data;
    }
      
    // Driver code
    public static void main(String[] args)
    {
        LinkedList ll = new LinkedList();
          
        /* Use push() function to construct 
        the below list 8 -> 23 -> 11 -> 29 -> 12 */
        ll.push(12);
        ll.push(29);
        ll.push(11);
        ll.push(23);
        ll.push(8);
        System.out.println(ll.findSecondLastNode(ll.start));
    }
}
  
// This code is Contributed by Adarsh_Verma

# Python3 program to find the second last node
# of a linked list in single traversal
import math
  
# Link list node
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
  
# Function to find the second last
# node of the linked list
def findSecondLastNode(head):
    temp = head
  
    # If the list is empty or 
    # contains less than 2 nodes
    if (temp == None or temp.next == None):
        return -1
  
    # Traverse the linked list
    while (temp != None):
  
        # Check if the current node is the
        # second last node or not
        if (temp.next.next == None):
            return temp.data
              
        # If not then move to the next node
        temp = temp.next
  
# Function to push node at head
def push(head, new_data):
    new_node = Node(new_data)
    #new_node.data = new_data
    new_node.next = head
    head = new_node
    return head
  
# Driver code
if __name__ == '__main__':
      
    # Start with the empty list
    head = None
  
    # Use push() function to construct
    # the below list 8 . 23 . 11 . 29 . 12
    head = push(head, 12)
    head = push(head, 29)
    head = push(head, 11)
    head = push(head, 23)
    head = push(head, 8)
  
    print(findSecondLastNode(head))
  
# This code is contributed by Srathore

// C# program to find the second last node 
// of a linked list in single traversal
using System;
  
// Linked list node
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;
    }
      
    // Function to push node at head
    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;
        }
    }
      
    // method to find the second last 
    // node of the linked list 
    public int findSecondLastNode(Node ptr)
    {
        Node temp = ptr;
          
        // If the list is empty or contains less 
        // than 2 nodes
        if(temp == null || temp.next == null)
            return -1;
      
            // This loop stops at second last node
        while(temp.next.next != null)
        {
            temp = temp.next;
        }
        return temp.data;
    }
      
    // Driver code
    public static void Main()
    {
        LinkedList ll = new LinkedList();
          
        /* Use push() function to construct 
        the below list 8 -> 23 -> 11 -> 29 -> 12 */
        ll.push(12);
        ll.push(29);
        ll.push(11);
        ll.push(23);
        ll.push(8);
        Console.WriteLine(ll.findSecondLastNode(ll.start));
    }
}
  
// This code is contributed by PrinciRaj1992

<script>
  
// Javascript program to find the second last node
// of a linked list in single traversal
  
// Link list node
  
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
  
// method to find the second last
// node of the linked list
function findSecondLastNode( ptr)
{
var temp = head ;
  
// If the list is empty or
// contains less than 2 nodes
if (temp == null || temp.next == null)
return -1 ;
  
// Traverse the linked list
while (temp != null)
{
  
// Check if the current node is the
// second last node or not
if (temp.next.next == null)
return temp.data;
  
// If not then move to the next node
temp = temp.next;
}
}
  
// Function to push node at head
function push( data)
{
var new_node = new Node(data) ;
new_node.next = head ;
head = new_node ;
return head ;
}
  
// Driver Code
  
var head = null ;
  
/* Use push() function to construct 
the below list 8 -> 23 -> 11 -> 29 -> 12 */
  
head = push(12);
head = push(29);
head = push(11);
head = push(23);
head = push(8);
document.write(findSecondLastNode(head));
  
// This code is contributed by jana_sayantan.
</script>

29

Complejidad del tiempo : O(n)