Tolkien wrote The Lord of the Rings in whatever hours a full Oxford professorship left over, which usually meant late at night. The whole thing took about twelve years, and it grew out of invented languages he'd been building since he was a teenager. He worked slowly, by hand, and rewrote constantly.

The Direct Answer
Slowly and by hand over roughly twelve years, mostly late at night, with the invented languages built first.
He said the languages were the foundation and the stories grew to give them a world, in his 1955 letter to his American publisher (Letters, No. 165).

Languages First, Story Second

Long before Frodo or the Ring existed, there was Elvish. Tolkien started inventing languages as a schoolboy and never stopped, refining Quenya and Sindarin with the seriousness of the professional philologist he became. The mythology of Middle-earth arrived partly as a home for those tongues. A language needs speakers, speakers need a history, and a history needs a world. That's roughly the order in which he built things.

The invention of languages is the foundation. The 'stories' were made rather to provide a world for the languages than the reverse. To me a name comes first and the story follows.

J.R.R. Tolkien, The Letters of J.R.R. Tolkien, No. 165

So the drafting rarely started from plot. A name would surface, carrying a sound and a feeling, and the story would follow it. Rivendell, Lothlorien, Gondor: these were words he loved before they were places on a map. Plenty of writers outline a plot and bolt the names on afterward. Tolkien trusted the words to tell him what the world was.

Twelve Years, Mostly After Dark

He began the sequel to The Hobbit in December 1937, after his publisher asked for more about hobbits. He finished the writing around 1949, and the three volumes came out in 1954 and 1955. For all twelve of those years he was teaching, marking exams, sitting on committees, and raising four children, so the fiction lived at the edge of the day. He wrote after the house went quiet, often past midnight.

The method was longhand first, then a typed fair copy he pecked out himself with two fingers because he couldn't afford a typist. He rewrote obsessively, sometimes redoing a chapter many times over before he was satisfied. During Oxford's terms whole weeks could pass with no progress at all. Then a vacation would arrive and the pages would come in a rush. He also read the chapters aloud to the Inklings, the Oxford circle that included C.S. Lewis, whose steady encouragement Tolkien later credited with keeping the book alive.

Some of those chapters traveled a long way before they were done. During the Second World War his son Christopher was posted to South Africa with the RAF, and Tolkien mailed him the new sections as they were drafted, with running commentary on where the story might be heading. The letters became a private serial, another reader waiting at the far end of a very slow post, and that waiting reader was part of what kept the pages coming.

For the daily rhythm, the study, and the Inklings in full, see the full J.R.R. Tolkien writing routine.

What You Can Steal