如何在遇到值大于x时删除链表右侧所有节点？求最优解

First, let’s recap the core requirement to stay aligned:

• Delete all nodes to the right of the first node whose value exceeds x
• If the head node itself is greater than x, delete the entire list (return null)

Looking at your current implementation, there are a few bugs and inefficiencies to address:

• It fails the case where the head node is greater than x (e.g., input 7 1 2 6 with x=6 should return null, but your code returns the original head node)
• Redundant loops (like traversing to the end of the list just to set prev.next = null—this can be done in one step)
• Overcomplicated branching that makes the code harder to read and maintain

Optimized Solution #

Here’s a cleaner, more efficient implementation that fixes these issues and meets all your requirements:

Node Delete(Node head, int value) {
    // Handle empty list case
    if (head == null) return head;
    
    // If head is greater than value, delete the entire list
    if (head.data > value) {
        return null;
    }
    
    Node current = head;
    // Traverse to the last node that's <= value
    while (current.next != null && current.next.data <= value) {
        current = current.next;
    }
    
    // Cut off all nodes after this point
    current.next = null;
    return head;
}

How This Works (Matching Your Examples) #

Let’s walk through each test case to verify:

1. Input: 5 1 2 6, x=5
   • We start at 5 (<=5), move to 1 (<=5), then to 2 (<=5)
   • current.next is 6 (which is >5), so we stop
   • Set 2.next = null, returning the list 5 1 2 (correct)
2. Input: 7 1 2 6, x=6
   • Head node 7 is >6, so we immediately return null (correct)
3. Input: 5 4 7 6, x=6
   • Start at 5 (<=6), move to 4 (<=6)
   • current.next is 7 (which is >6), so we stop
   • Set 4.next = null, returning the list 5 4 (correct)

Key Improvements #

• Time Complexity: Still O(n) (we traverse the list once at most), same as your original code—but with fewer unnecessary operations
• Readability: Simplified logic with minimal branching, making it easier to debug and maintain
• Bug Fixes: Correctly handles the case where the head node exceeds x
• Efficiency: No redundant loops—we directly cut the list as soon as we find the first node that exceeds x

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