Locating the Tail Node (Last Node) in a Linked List

In a linked list, the tail node is the last node in the sequence of all connected nodes. The tail node’s next pointer is typically set to null indicating that there are no more nodes in the sequence. Finding the tail node is important for several reasons: it allows for efficient insertion at the end of the list in O(1) time if a tail pointer is maintained, facilitates reverse traversal in doubly linked lists, and is essential for operations like appending one list to another.

Prerequisites: Basics of Linked List Data Structure, Creating and Connecting Nodes in a Linked List, Traversing a Linked List Data Structure.

Problem Statement

Given the head node of a singly linked list, find and return the last node in the list. This task involves traversing the entire list until we reach a node whose next pointer is null, indicating it’s the last node.

Example:

Consider the following linked list:

1 -> 7 -> 3 -> 9 -> null

In this example:

The head node contains the value 1
The tail node (last node) contains the value 9
The next pointer of the tail node is null

The goal is to develop an algorithm that, when given the head node (the node containing 1), will return the tail node (the node containing 9).

Algorithm

To find the tail node of a singly linked list, we can use a simple iterative approach. This method involves traversing the list from the head node until we reach the last node, which is identified by its null next pointer.

Here’s a step-by-step algorithm using a while loop:

Check if the input head is null. If so, return null as there is no tail in an empty linked list.
Initialize a pointer current and point it to the head of the given linked list.
While current.next is not null:
- Update current to current.next.
Return current, which now points to the tail node.

This algorithm has a time complexity of O(n), where n is the number of nodes in the list, as we may need to traverse the entire list to reach the tail. The space complexity is O(1) since we only use a single additional pointer regardless of the list’s size.

Implementation

Below is the implementation of iterative approach to find the tail node of a given linked list:


# Definition of the Node class for the linked list
class Node:
  def __init__(self, data):
    self.data = data
    self.next = None

def find_tail(head):
  # Check if the input head is None
  if head is None:
    return None  # Return None as there is no tail in an empty list
  
  # Initialize a pointer 'current' to the head of the list
  current = head
  
  # Traverse the list until we reach the last node
  while current.next is not None:
    # Update current to the next node
    current = current.next
  
  # Now the current node points to the last node (tail)
  # So let's return it
  return current

# Helper function to create a linked list from a list of values
def create_linked_list(values):
  if not values:
    return None
  head = Node(values[0])
  current = head
  for value in values[1:]:
    current.next = Node(value)
    current = current.next
  return head

# Helper function to print the linked list
def print_linked_list(head):
  current = head
  while current:
    print(current.data, end=" -> ")
    current = current.next
  print("None")

# Example usage
if __name__ == "__main__":
  # Create a sample linked list: 1 -> 2 -> 3 -> 4 -> 5
  values = [1, 2, 3, 4, 5]
  head = create_linked_list(values)
  
  print("Original linked list:")
  print_linked_list(head)
  
  # Find the tail of the linked list
  tail = find_tail(head)
  
  if tail:
    print(f"The tail of the linked list is: {tail.data}")
  else:
    print("The linked list is empty.")


#include <stdio.h>
#include <stdlib.h>

// Definition of the Node struct for the linked list
struct Node {
  int data;
  struct Node* next;
};

// Function to find the tail of the linked list
struct Node* find_tail(struct Node* head) {
  // Check if the input head is NULL
  if (head == NULL) {
    return NULL;  // Return NULL as there is no tail in an empty list
  }
  
  // Initialize a pointer 'current' to the head of the list
  struct Node* current = head;
  
  // Traverse the list until we reach the last node
  while (current->next != NULL) {
    // Update current to the next node
    current = current->next;
  }
  
  // Now the current node points to the last node (tail)
  // So let's return it
  return current;
}

// Helper function to create a linked list from an array of values
struct Node* create_linked_list(int values[], int size) {
  if (size == 0) {
    return NULL;
  }
  struct Node* head = (struct Node*)malloc(sizeof(struct Node));
  head->data = values[0];
  head->next = NULL;
  struct Node* current = head;
  for (int i = 1; i < size; i++) {
    current->next = (struct Node*)malloc(sizeof(struct Node));
    current = current->next;
    current->data = values[i];
    current->next = NULL;
  }
  return head;
}

// Helper function to print the linked list
void print_linked_list(struct Node* head) {
  struct Node* current = head;
  while (current != NULL) {
    printf("%d -> ", current->data);
    current = current->next;
  }
  printf("NULL\n");
}

// Helper function to free the memory allocated for the linked list
void free_linked_list(struct Node* head) {
  struct Node* current = head;
  struct Node* next;
  while (current != NULL) {
    next = current->next;
    free(current);
    current = next;
  }
}

int main() {
  // Create a sample linked list: 1 -> 2 -> 3 -> 4 -> 5
  int values[] = {1, 2, 3, 4, 5};
  int size = sizeof(values) / sizeof(values[0]);
  struct Node* head = create_linked_list(values, size);
  
  printf("Original linked list:\n");
  print_linked_list(head);
  
  // Find the tail of the linked list
  struct Node* tail = find_tail(head);
  
  if (tail != NULL) {
    printf("The tail of the linked list is: %d\n", tail->data);
  } else {
    printf("The linked list is empty.\n");
  }
  
  // Free the memory allocated for the linked list
  free_linked_list(head);
  
  return 0;
}


#include <iostream>
#include <vector>

using namespace std;

// Definition of the Node class for the linked list
class Node {
public:
  int data;
  Node* next;
  
  Node(int value) : data(value), next(nullptr) {}
};

Node* find_tail(Node* head) {
  // Check if the input head is nullptr
  if (head == nullptr) {
    return nullptr;  // Return nullptr as there is no tail in an empty list
  }
  
  // Initialize a pointer 'current' to the head of the list
  Node* current = head;
  
  // Traverse the list until we reach the last node
  while (current->next != nullptr) {
    // Update current to the next node
    current = current->next;
  }
  
  // Now the current node points to the last node (tail)
  // So let's return it
  return current;
}

// Helper function to create a linked list from a vector of values
Node* create_linked_list(const vector<int>& values) {
  if (values.empty()) {
    return nullptr;
  }
  Node* head = new Node(values[0]);
  Node* current = head;
  for (size_t i = 1; i < values.size(); ++i) {
    current->next = new Node(values[i]);
    current = current->next;
  }
  return head;
}

// Helper function to print the linked list
void print_linked_list(Node* head) {
  Node* current = head;
  while (current) {
    cout << current->data << " -> ";
    current = current->next;
  }
  cout << "nullptr" << endl;
}

// Helper function to free the memory allocated for the linked list
void free_linked_list(Node* head) {
  Node* current = head;
  while (current) {
    Node* temp = current;
    current = current->next;
    delete temp;
  }
}

int main() {
  // Create a sample linked list: 1 -> 2 -> 3 -> 4 -> 5
  vector<int> values = {1, 2, 3, 4, 5};
  Node* head = create_linked_list(values);
  
  cout << "Original linked list:" << endl;
  print_linked_list(head);
  
  // Find the tail of the linked list
  Node* tail = find_tail(head);
  
  if (tail) {
    cout << "The tail of the linked list is: " << tail->data << endl;
  } else {
    cout << "The linked list is empty." << endl;
  }

  // Free the memory allocated for the linked list
  free_linked_list(head);

  return 0;
}


// Definition of the Node class for the linked list
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

function findTail(head) {
  // Check if the input head is null
  if (head === null) {
    return null;  // Return null as there is no tail in an empty list
  }
  
  // Initialize a pointer 'current' to the head of the list
  let current = head;
  
  // Traverse the list until we reach the last node
  while (current.next !== null) {
    // Update current to the next node
    current = current.next;
  }
  
  // Now the current node points to the last node (tail)
  // So let's return it
  return current;
}

// Helper function to create a linked list from an array of values
function createLinkedList(values) {
  if (values.length === 0) {
    return null;
  }
  const head = new Node(values[0]);
  let current = head;
  for (let i = 1; i < values.length; i++) {
    current.next = new Node(values[i]);
    current = current.next;
  }
  return head;
}

// Helper function to print the linked list
function printLinkedList(head) {
  let current = head;
  let result = '';
  while (current) {
    result += current.data + ' -> ';
    current = current.next;
  }
  result += 'null';
  console.log(result);
}

// Example usage
function main() {
  // Create a sample linked list: 1 -> 2 -> 3 -> 4 -> 5
  const values = [1, 2, 3, 4, 5];
  const head = createLinkedList(values);
  
  console.log("Original linked list:");
  printLinkedList(head);
  
  // Find the tail of the linked list
  const tail = findTail(head);
  
  if (tail) {
    console.log(`The tail of the linked list is: ${tail.data}`);
  } else {
    console.log("The linked list is empty.");
  }
}

// Call the main function
main();


import java.util.Arrays;

public class Main {
  // Definition of the Node class for the linked list
  static class Node {
    int data;
    Node next;

    Node(int data) {
      this.data = data;
      this.next = null;
    }
  }

  public static Node findTail(Node head) {
    // Check if the input head is null
    if (head == null) {
      return null;  // Return null as there is no tail in an empty list
    }
    
    // Initialize a pointer 'current' to the head of the list
    Node current = head;
    
    // Traverse the list until we reach the last node
    while (current.next != null) {
      // Update current to the next node
      current = current.next;
    }
    
    // Now the current node points to the last node (tail)
    // So let's return it
    return current;
  }

  // Helper function to create a linked list from an array of values
  public static Node createLinkedList(int[] values) {
    if (values.length == 0) {
      return null;
    }
    Node head = new Node(values[0]);
    Node current = head;
    for (int i = 1; i < values.length; i++) {
      current.next = new Node(values[i]);
      current = current.next;
    }
    return head;
  }

  // Helper function to print the linked list
  public static void printLinkedList(Node head) {
    Node current = head;
    while (current != null) {
      System.out.print(current.data + " -> ");
      current = current.next;
    }
    System.out.println("null");
  }

  public static void main(String[] args) {
    // Create a sample linked list: 1 -> 2 -> 3 -> 4 -> 5
    int[] values = {1, 2, 3, 4, 5};
    Node head = createLinkedList(values);
    
    System.out.println("Original linked list:");
    printLinkedList(head);
    
    // Find the tail of the linked list
    Node tail = findTail(head);
    
    if (tail != null) {
      System.out.println("The tail of the linked list is: " + tail.data);
    } else {
      System.out.println("The linked list is empty.");
    }
  }
}

Applications

Finding the tail node in a linked list is a fundamental operation with several important applications:

Efficient Insertion at the End: Maintaining a tail pointer allows for O(1) time complexity insertions in scenarios where frequent insertions at the end of a list are required. This is particularly useful in queue implementations using linked lists, where elements are added to the rear.
List Concatenation: When merging two linked lists, we need to find the tail node of the first list and connect it to the head node of the next list. This operation is common in file systems for combining fragmented file blocks.
Reverse Traversal in Doubly Linked Lists: For doubly linked lists, the tail node serves as the starting point for backward traversal. This is beneficial in applications like browser history navigation, where users need to move backwards through previously visited pages.

The problem of finding the tail node in a linked list is fundamental and can be extended to several related problems and variations:

Finding the Nth Node from the End: This problem involves locating a specific node in a linked list, counting from the end. For example, if asked to find the 3rd node from the end in a list of 10 nodes, you would need to identify the 8th node from the beginning.
Middle of the Linked List: This operation aims to find the central node in a linked list. In a list with an odd number of nodes, it’s straightforward. For even-numbered lists, it’s typically defined as the first of the two middle nodes.
Detect a Cycle in a Linked List: This problem focuses on determining if a linked list contains a loop where the tail points back to a previous node. Such a cycle would result in an infinite traversal if not detected.
Intersection of Two Linked Lists: This operation aims to find the node at which two separate linked lists intersect or join. After the intersection point, both lists would share the same nodes.
Rotate List: This problem involves shifting all nodes in a linked list to the right by a given number of positions. For example, rotating the list 1 -> 2 -> 3 -> 4 -> 5 by 2 positions would result in 4 -> 5 -> 1 -> 2 -> 3. These problems often employ similar techniques to the tail-finding problem: