AK
BAN USERNot mentioning the syntactical rules, the problem lies in the algorithm. the algorithm wants to check all the nodes inside the list but it will not be able to in some conditions
The list nodes are being deleted inside a for loop which runs for the length of the list. this will create problems and may not iterated over the entire list which would be a bug.
for example, assume that the list has 5 nodes, so the list length is 5. let the iteration counter be equal to 3 (i=3) so that the 4th node is being checked, let it satisfy the condition and be removed so that the list length now is equal to 4. however, 'i' is 3 in current iteration. after removal, i would be incremented to 4.
now, we have only compared the 4th node with i=3, deleted it and incremented i to 4. length is also 4 since we have removed a node from the list. so now, when the condition in for loop is checked again, it says that 'i' should be less that length of list. since both are equal to 4, the flow will exit from the for loop and the last node of the list will not be checked.
The best idea is to run inside a while loop and see if the current node is the last node of the list.
node structure ->
1. previous node link called previous
2. next node link called next
3. data
---------------
Algo:
1. start
2. set temp to next
3. set next to prev
4. set prev to temp
5. advance current position (var pointing to the current position in the list) to next node
6. start from step 2 again
the solution has to be O(1) and not O(n)
- AK September 29, 2010