如何从单链表获取前n个值？头插法更优实现方案咨询

Hey there! Let's break down your two linked list questions one by one—happy to share some practical insights here 😊

1. Getting the First n Values of a Singly Linked List #

First up, grabbing the first n values from a singly linked list. The key here is handling edge cases first, then doing a straightforward traversal.

Step-by-Step Approach: #

• Check for invalid inputs: If the list is empty, or n is ≤ 0, return an empty list right away—no need to do extra work.
• Traverse and collect: Use a pointer to walk through the list, collecting values until we've grabbed n elements or reached the end of the list (in case n is larger than the total number of nodes).

Example Code (Python): #

First, let's define our basic ListNode structure:

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

Then the function to get the first n values:

def get_first_n_values(head, n):
    # Handle edge cases upfront
    if not head or n <= 0:
        return []
    
    result = []
    current_node = head
    count = 0
    
    # Traverse until we have n values or hit the end of the list
    while current_node and count < n:
        result.append(current_node.val)
        current_node = current_node.next
        count += 1
    
    return result

This is robust because it handles cases where n is larger than the list length (it just returns all available values) and avoids unnecessary iterations.

2. Optimal Head Insertion for Singly Linked Lists #

Your idea of inserting at the tail then reversing the list works, but it's not efficient—you're doing two full traversals of the list (O(n) time each), which adds up to O(n) total time. There's a way better approach that takes O(1) time (constant time, regardless of list length).

The Optimal Method: Direct Head Pointer Manipulation #

Instead of traversing to the tail, we can directly wire the new node to be the new head:

1. Create a new node with your desired value.
2. Set the new node's next pointer to point to the current head of the list.
3. Update the list's head pointer to point to this new node.

That's it—no traversal needed, just three quick operations.

Example Code (Python): #

Standalone Function:

def insert_at_head(head, val):
    new_node = ListNode(val)
    # Point new node to the existing head
    new_node.next = head
    # Update head to be the new node
    head = new_node
    return head

If Using a Linked List Class:

If you're wrapping the list in a class (common practice), it's even cleaner:

class SinglyLinkedList:
    def __init__(self):
        self.head = None
    
    def insert_at_head(self, val):
        new_node = ListNode(val)
        new_node.next = self.head
        self.head = new_node

Why This Is Better: #

• Time Efficiency: Direct insertion is O(1), while tail-insert-then-reverse is O(n). For a list with 10,000 nodes, that's a massive difference—1 operation vs. 20,000 operations.
• Simplicity: No need to write reversal logic or handle edge cases for tail insertion (like empty lists). It's straightforward and less error-prone.

内容的提问来源于stack exchange，提问作者P. Bolfa