Start with the adjustment. It might be a good idea to pull the linkage all the way off. That way you can cycle the transmission through the gears and put it all the way in park where the detent centers it in park. Get out from under the truck and try pushing it. If it works like it should, then you can adjust and install the linkage.
If you loosen the linkage enough, you should be able to do this without removal. I suggested removal so you don't get it just enough adjusted and leave it. That will just have you back down there in a few weeks doing the same thing.