SPOJ题目CLSLDR循环双向链表实现超时，求问题排查

Hey there! Let's break down why your code is hitting a Time Limit Exceeded (TLE) error and how to fix it.

The Core Problem: O(n) Lookup for the Last Element After Each Deletion #

Your current approach uses an O(n) algorithm to find the last element every time you delete the p-th node. This drives the overall time complexity to O(n²). For large values of n (like the upper limits in SPOJ problems, which can be 10^5 or more), this is way too slow—10^10 operations will never finish within the time window.

Why This Happens #

Circular doubly linked lists are great for efficient deletions, but wasting time traversing the entire list to find a starting point after each deletion negates that advantage. You don't need to re-find the "last element" every time—you can track your position dynamically.

Fixes to Optimize Your Code #

Here are concrete changes to get your code running within time limits:

1. Maintain a Current Position Pointer #

Instead of resetting to the start of the list every time, keep a pointer that tracks where you'll begin counting for the next deletion. After deleting a node, update this pointer to point to the next node of the deleted element (since that's where the next count should start).

For example, if you delete node target, set:

current = target->next;

This way, you never have to traverse the entire list to find your starting point again.

2. Reduce Count Steps with Modulo #

If p is larger than the current length of the list, use modulo arithmetic to avoid unnecessary loops. Before counting p steps, compute:

int steps = p % current_length;
// If steps is 0, we need to delete the last element (since p is a multiple of current_length)
if (steps == 0) steps = current_length;

This cuts down the number of steps you need to traverse from p to at most current_length-1, which is a huge time saver for large p.

3. Update List Length Dynamically #

Keep a variable that tracks the current number of nodes in the list. Decrement it by 1 every time you delete a node. This makes the modulo operation above efficient and avoids having to count nodes each time.

Example Adjustment to Your Code Snippet #

Here's how you might integrate these changes with your existing deleteNode function:

// Assume we have:
// Node* current; // Tracks the starting point for next count
// int len; // Current length of the list

// Calculate steps to move
int steps = p % len;
if (steps == 0) steps = len;

// Move current to the node to delete
for (int i = 1; i < steps; i++) {
    current = current->next;
}

Node* target = current;
// Delete the target node
deleteNode(target);

// Update current pointer and length
current = target->next;
len--;

Why This Works #

With these changes, the overall time complexity drops to O(n). Each node is deleted exactly once, and each traversal step is constant time (thanks to modulo and the current pointer). This is efficient enough for even the largest input sizes in SPOJ problems.

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