Implementing remove command in command pattern

I am implementing the command pattern in my c++ QT application. I am building a node based editor. There are commands such as AddNode, MoveNode, and RemoveNode.

Now say I first add a node with the add command, then move it using the move command, and lastly delete it again using the remove command.

If I now start undoing I start getting into problems. The first undo will undo the deletion and recreate the node. If I undo again the move should be undone. This however proofs to be impossible because the node is now sitting at a new memory address, so the pointer in the MoveCommand can no longer be used to undo the move.

I see two possible solutions:

One: Not storing pointers in the commands, but identifiers, then use hashmaps that have information about the addresses belonging to the identifiers. This does however seem like quite a makeshift solution to me, that will become error prone when complexion rises.

Two: Not actually deleting the nodes, but instead keeping them alive from the command object. The problem from this is that it becomes hard to manage in the part of the code where I actually use the nodes, and then have to flag all nodes that exist but are not in use.

Do any of you have experience with this, and how did you solve this problem?

Many thanks!