I have a program that does not compile because a return value has the wrong lifetime, and I cannot change the lifetime it came from because the method becomes incompatible with the Iterator trait. The most confusing part is that a version of the exact same code with non-mutable references compiles perfectly fine.
What is the difference, and what can I do to fix this?
This is really a loaded question. Let's unwrap it one piece at a time:
This code is rejected because next cannot return a value with a lifetime that is "disconnected" from the lifetime in &mut self (the error message calls this lifetime '1 as in &'1 mut self). There is no trait bound indicating that '1: 'a.
The general form of this API is known as a "lending" or "streaming" iterator. E.g. an iterator that lends contents that it owns. You can read more about this pattern (and problems and workarounds) in:
Immutable references can be copied (and cloned), mutable references cannot. You can only return a mutable reference from behind another mutable reference if you re-borrow it, but the re-borrow cannot live longer than its "source".
The Iterator trait requires that the lifetime of the Item be unrelated to the lifetime of Self, otherwise it would not be possible to handle multiple items simultaneously (e.g. collect()). This can be achieved by copying out immutable references from behind an iterator, but it doesn't work with mutable references.
And indeed, if you think about it: handing out multiple simultaneous mutable references to nodes of a linked list would be unsound if it were possible (a parent transitively points to all of its children, so a mutable parent reference co-existing with mutable child references would lead to mutable aliasing, hence UB).