How to find nth element from the end of a singly linked list?

Finding the nth element from the end of a single-linked list is a common data structure problem that can typically be solved using the following methods:

Method One: Two-pass Traversal

Steps:

1. First Traversal: Traverse the entire linked list to determine its total length L.
2. Second Traversal: Traverse to the (L-n+1)th node from the head, which corresponds to the nth node from the end.

Example Code (assuming Python):

python
class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def find_nth_from_end(head, n):
    # First traversal: calculate the linked list length
    length = 0
    current = head
    while current:
        length += 1
        current = current.next

    # Calculate the target index from the head
    target_index = length - n
    if target_index < 0:
        return None  # n exceeds the list length, return None

    # Second traversal: find the target node
    current = head
    for _ in range(target_index):
        current = current.next

    return current

Method Two: Two-pointer Method (Fast and Slow Pointer Method)

Steps:

1. Initialize two pointers: Both pointers point to the head node.
2. Move the fast pointer: Advance the fast pointer forward by n nodes.
3. Move both pointers simultaneously: Move both pointers at the same time; when the fast pointer reaches the end of the linked list, the slow pointer points exactly to the nth node from the end.

Example Code:

python
def find_nth_from_end(head, n):
    fast = slow = head
    # Move the fast pointer forward by n steps
    for _ in range(n):
        if fast is None:
            return None  # n exceeds the list length, return None
        fast = fast.next

    # Move both pointers simultaneously until fast reaches the end
    while fast:
        slow = slow.next
        fast = fast.next

    return slow

Among the two methods, Method Two is superior because it can locate the required node in a single traversal with a time complexity of O(L) and a space complexity of O(1). Method One also has a time complexity of O(L), but it requires two traversals of the linked list. Based on efficiency considerations, Method Two (the two-pointer method) is typically the better choice.

There are several common methods to find the nth element from the end of a singly linked list. I will introduce two primary methods and provide a relevant example.

Method One: Two-Pointer Method (Fast and Slow Pointer Method)

The two-pointer method is highly efficient. The idea is to use two pointers—a fast pointer and a slow pointer. Steps are as follows:

1. First, advance the fast pointer by n nodes.
2. Then, both pointers move simultaneously until the fast pointer reaches the end of the list.
3. When the fast pointer reaches the end, the slow pointer will point to the nth node from the end.

Example Code (Python):

python
class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def find_nth_from_end(head, n):
    fast = slow = head
    for _ in range(n):
        if not fast:
            return None
        fast = fast.next

    while fast:
        fast = fast.next
        slow = slow.next

    return slow.value

Method Two: Calculating List Length

Another approach is to first traverse the entire list to determine its length, then traverse again to the specified position. Steps are as follows:

1. Traverse the entire list to determine its length L.
2. Starting from the head, move to the (L - n + 1)th node, which is the nth node from the end.

Example Code (Python):

python
class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def find_nth_from_end(head, n):
    length = 0
    current = head
    while current:
        length += 1
        current = current.next

    if n > length:
        return None

    current = head
    for _ in range(length - n):
        current = current.next

    return current.value

Evaluation

The two-pointer method is superior because it traverses the list only once with a time complexity of O(L), where L is the length of the list. In contrast, the method that calculates the length requires two traversals of the list, making it less efficient. In practical applications, if frequent lookups from the end of the list are needed, the two-pointer method is more suitable. For occasional operations, both methods can be used.

The problem of finding the nth element from the end of a singly linked list can be solved using two primary methods: the two-pass method and the two-pointer method (also known as the fast and slow pointers method). I will provide a detailed explanation of both methods and include relevant code examples.

Method One: Two-Pass Method

1. First traversal: Traverse the entire list to determine its total length L.
2. Second traversal: Traverse the list to the (L-n) position, which corresponds to the nth element from the end.

Code Example (Python):

python
class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

def find_nth_from_end(head, n):
    length = 0
    current = head
    # First traversal: Calculate the total length of the list
    while current:
        length += 1
        current = current.next

    # Calculate the target position
    target = length - n
    current = head
    # Second traversal to the target position
    while target > 0:
        current = current.next
        target -= 1

    return current.value if current else "Node does not exist"

Method Two: Two-Pointer Method

The two-pointer method requires only one traversal and can find the result more efficiently.

1. Initialize two pointers: fast and slow, both pointing to the head node.
2. Move the fast pointer: Advance fast forward n steps.
3. Move both pointers simultaneously: While fast is not null (i.e., fast.next is not null), advance both fast and slow forward. When fast reaches the end node, slow will point to the nth element from the end.

Code Example (Python):

python
def find_nth_from_end_two_pointers(head, n):
    fast = slow = head
    # fast moves forward n steps
    for _ in range(n):
        if fast is None:
            return "Node does not exist"
        fast = fast.next

    # Move both fast and slow simultaneously
    while fast:
        fast = fast.next
        slow = slow.next

    return slow.value if slow else "Node does not exist"

Both methods effectively solve this problem, with the two-pointer method typically being more efficient as it requires only one traversal. When addressing practical scenarios, the choice of method depends on specific requirements and constraints. For instance, if memory usage is constrained, the two-pointer method is preferred to minimize traversal count.