链表操作技术求助：删除第n个元素及相关操作疑问

Hey Alexia, let's break down your linked list questions one by one—this stuff can feel tricky at first, but once you get the hang of pointer manipulation, it clicks!

First, let's define a basic ListNode class we'll use for all examples (this is standard for linked list implementations):

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

This is straightforward—just traverse the list from head to tail, counting each node as you go. No fancy tricks here:

def get_length(head):
    count = 0
    current = head
    while current:
        count += 1
        current = current.next
    return count

It runs in O(n) time since we have to visit every node once.

First, clarify: are you using 1-based or 0-based indexing? I'll assume 1-based (since you said "第n个元素")—adjust the code slightly if you need 0-based.

The biggest pain point here is handling edge cases (like deleting the first node) and correctly linking the remaining nodes. A dummy node (a fake head that points to your actual list head) is a lifesaver—it eliminates the need for separate logic when deleting the original head.

Step-by-step approach: #

• Create a dummy node with next pointing to your list head.
• Use two pointers: prev starting at the dummy, current starting at the head.
• Move current forward n-1 times so it lands on the nth node.
• Update prev.next to skip the nth node (point directly to current.next).
• Return dummy.next (this handles cases where we deleted the original head).

Code example: #

def remove_nth_node(head, n):
    dummy = ListNode(0, head)
    prev = dummy
    current = head
    
    # Move current to the nth node
    for _ in range(n-1):
        if not current:
            return head  # n is larger than the list length
        current = current.next
    
    # Skip the nth node to complete the deletion
    prev.next = current.next
    # In languages like C++, you'd manually delete `current` to free memory here
    
    return dummy.next

How the linking works: #

You don't need to "rebuild" the list—you just adjust the pointer of the node before the deleted one (prev) to bypass the node you're removing. The deleted node is no longer referenced, so it gets garbage-collected automatically in Python (or needs manual cleanup in lower-level languages).

Edge cases to watch for: #

• Deleting the first node: The dummy's next will point to head.next, which becomes the new head of the list.
• Deleting the last node: current.next will be None, so prev.next becomes None, correctly terminating the list.

Let's cover each insertion scenario with clear examples.

3.1 头部插入 #

Super simple—create a new node, set its next to the current head, then make the new node the new head:

def insert_at_head(head, val):
    new_node = ListNode(val)
    new_node.next = head
    return new_node  # This is your updated list head

3.2 尾部插入 #

Traverse to the last node (where next is None), then set its next to the new node. If the list is empty, the new node becomes the head:

def insert_at_tail(head, val):
    new_node = ListNode(val)
    if not head:
        return new_node
    current = head
    while current.next:
        current = current.next
    current.next = new_node
    return head

3.3 倒数第n个位置插入 #

Use the two-pointer technique to find the insertion point without first calculating the list length (though calculating length works too if you prefer). We want to insert the new node right before the nth node from the end:

def insert_at_nth_from_end(head, val, n):
    dummy = ListNode(0, head)
    slow = fast = dummy
    
    # Move fast pointer n steps ahead
    for _ in range(n):
        if not fast:
            return head  # n is larger than the list length
        fast = fast.next
    
    # Move both pointers until fast reaches the end
    while fast.next:
        slow = slow.next
        fast = fast.next
    
    # Insert the new node between slow and slow.next
    new_node = ListNode(val)
    new_node.next = slow.next
    slow.next = new_node
    
    return dummy.next

• If n equals the list length, this inserts at the head.
• If n=1, this inserts at the tail.

Short answer: No, you never need to recreate the entire list for these operations. Linked lists are designed for in-place modifications—all you're doing is adjusting pointers to add, remove, or rearrange nodes. Recreating the list would be inefficient (O(n) time and space) when you can do the same work in O(n) time with O(1) extra space (except for the new node you insert, which is necessary).

Only recreate the list if the problem specifically asks for a new list (e.g., "return a copy of the list with the nth node removed")—but even then, you'd copy nodes one by one, not rebuild from scratch unnecessarily.

内容的提问来源于stack exchange，提问作者Alexia Desouza