I drove Brissy to Katherine in the early '90s in a 10yo Honda Accord. It took 3 days, only stopping to sleep & get fuel, and eating while driving. I stuck to the highways but still made sure I had tools, two spares, alternator belt, a can of Barrs Leaks, water etc. Even though there was some traffic, I didn't want to be stuck for something so easily repaired.
I had camping gear & chose to camp beside my car for the two nights needed. There are plenty of places where you can pull off the road. I rather liked my overnight on the Barkly Tableland.
For the return, I stayed overnight at a large truck stop in Mt Isa. Nothing fancy, but it was cheap. You got a single room, communal shower block and a typical truck stop restaurant.
Bring music, snacks & water.