The previous sample matches and removes leading space.
It's also possible with trailing space. With portable perl one can even include TABs
perl -pe 's/linux-\S+\s+//g'
Most exact is a "begin anchor" and trailing space becomes optional
perl -pe 's/(^|\s)linux-\S+\s*//g'
A recent GNU-Linux like Ubuntu can use sed -r instead of the perl -pe .
Just seeing the latter sample does not work because the trailing \s* consumes the leading space for a subsequent match.
Because I have no good idea for a fix, here is again one with leading spaces (and also allowing the beginning of the line):
Are you aware that these stipulations will exclude a "linux-something" at the lines end from being removed because there will be no space afterwards? Maybe this is not what you want. Also notice that your clause 2 means that the space immediately following the word "linux-*" will be removed too.
If your goal is indeed to remove the last match too i'd suggest:
sed 's/linux-[^ ]* \{0,1\}//g' /path/to/file
If you want to retain the blank following the word but would not want to add a space at the end of the string then this:
sed 's/linux-[^ ]*\( \{0,1\}\)/\1/g' /path/to/file
Any of the two work, because the apt command uses space as argument separator, when there are one or more spaces at the end they are ignored and two or more spaces in any place are condensed into one.