【初稿】 113バイト

g[x]=x
g(x:y:s)|x!!0==last y=g((y++tail x):s)|y!!0==last x=g((x++tail y):s)|1>0=g(x:s++[y])
main=interact$g.lines

家帰ってから、投稿記録見て焦った。。。
４０近く縮めなければならないとは。

【修正1】 110バイト

x%y=x!!0==last y
x!y=x++tail y
g[x]=x
g(x:y:s)|x%y=g(y!x:s)|y%x=g(x!y:s)|1>0=g(x:s++[y])
main=interact$g.lines

果てしなく遠い