Christopher Tolkien wrote four books in his History of Middle-earth series which go over the writing history of The Lord of the Rings in intricate details. It has multiple versions of many chapters, especially the early ones, and discusses the troubles Tolkien had going from "The Hobbit 2" to "A book so large it had to be split up because of paper shortage".
Therefore, most of the major changes were early in the writing history:
[The] most intractable problem lies in the development of the story through successive drafts, always changing but always closely dependent on what preceded. In the rather extreme case of the opening chapter 'A Long-expected Party', there are in this book six main texts to be considered and a number of abandoned openings.
However, once the story settled down, there are very few "drastic" changes. They are more of a slow evolution, with features emerging while the story was written, requiring the rewriting of earlier parts. Tolkien was basically building a house while constantly changing the foundations because it was getting too high.
I've come up with what I find are the most interesting changes in the fundamental direction of the story. This list is by no means complete, but it may serve as a starting point.
Note that most names went through a lot of changes. For example, the main character was originally called Bingo and Merry was Marmaduke. I will not comment on these names further.
The main character
Tolkien went through at least six different versions of the opening chapter. His main problem was with the ending of The Hobbit, where it is said that Bilbo "lived happily ever after".
The sequel to the Hobbit has remained where it stopped. It has lost my
favour, and I have no idea what to do with it. For one thing the original Hobbit was never intended to have a sequel - Bilbo 'remained very happy to the end of his days and those were extraordinarily long': a sentence I find an almost insuperable obstacle to a satisfactory link. For another nearly all the 'motives' that I can use were packed into the original book, so that a sequel will appear either 'thinner' or merely repetitional.
This is a summary of the different stages:
- Bilbo gives the party, aged 70. ('I am going to tell you a story about one of his descendants')
- Bilbo gives the party, aged 71.
- Bilbo married, and disappeared from Hobbiton with his wife (Primula Brandybuck) when he was 111. His son Bingo Baggins gives the party, aged 72.
- Bilbo, unmarried, adopted his young cousin Bingo Bolger (son of Primula Brandybuck), changed his name to Bingo Bolger-Baggins, and disappeared from Hobbiton when he was 111. His adopted cousin Bingo Bolger-Baggins gives the party, aged 72.
- Bilbo gives the Party at the age of 111 and vanishes at the end of it. Frodo departs quietly from Hobbiton with his friends 17 years later.
There was yet another projected plot, but it was never developed:
- Bilbo departs quietly from Hobbiton at the age of 111. Frodo ('Folco') gives the Party and vanishes at the end of it.
There are also many other notes, false starts, name changes and modifications to the party that set out from Hobbiton.
Gandalf or the Black Rider?
In the first draft of Three is Company, at the point where the Hobbits would later encounter the first Black Rider, they see Gandalf instead.
The sound of hoofs drew nearer. Round a turn came a white horse, and on it sat a bundle - or that is what it looked like: a small man wrapped entirely in a great cloak and hood so that only his eyes peered out, and his boots in the stirrups below.
The horse stopped when it came level with Bingo. The figure uncovered its nose and sniffed; and then sat silent as if listening. Suddenly a laugh came from inside the hood.
'Bingo my boy!' said Gandalf, throwing aside his wrappings.
Christopher Tolkien would say this:
Here this draft stops, at the foot of a page, and if my father continued beyond this point the manuscript is lost; but I think it far more likely that he abandoned it because he abandoned the idea that the rider was Gandalf as soon as written.
It is most curious to see how directly the description of Gandalf led into that of the Black Rider - and that the original sniff was Gandalf's! In fact the conversion of the one to the other was first carried out by pencilled changes on the draft text, thus:
Round a turn came a white [> black] horse, and on it sat a bundle - or that is what it looked like: a small [> short] man wrapped entirely in a great [added: black) cloak and hood so that only his eyes peered out [> so that his face was entirely shadowed]...
If the description of Gandalf in the draft is compared with that of the
Black Rider in the typescript text it will be seen that with further refinement the one still remains very closely based on the other. The new turn in the story was indeed 'unpremeditated'.
Strider the Hobbit
Aragorn started as "Trotter", a Hobbit with wooden shoes:
Suddenly Bingo noticed that a queer-looking, brown-faced hobbit, sitting in the shadows behind the others, was also listening intently. He had an enormous mug (more like a jug) in front of him, and was smoking a broken-stemmed pipe right under his rather long nose.
He was dressed in dark rough brown cloth, and had a hood on, in spite of the warmth, - and, very remarkably, he had wooden shoes! Bingo could see them sticking out under the table in front of him. [...]
'O! that is one of the wild folk - rangers we call 'em. He has been coming in now and again (in autumn and winter mostly) the last few years; but he seldom talks. Not but what he can tell some rare tales when he has a mind, you take my word.
What his right name is I never heard, but he's known round here as Trotter. You can hear him coming along the road in those shoes: clitter-clap - when he walks on a path, which isn't often. Why does he wear 'em? Well, that I can't say. But there ain't no accounting for East or West, as we say here, meaning the Rangers and the Shire-folk, begging your pardon.'
Like the Gandalf/Black Rider conversion above, it is always interesting to see how close the early texts are to the final version, but yet so far. Tolkien would ask "Who is Trotter?" many times in his notes.
Rangers are best not as hobbits, perhaps. But either Trotter (as a ranger) must be not a hobbit, or someone very well known: e.g. Bilbo. But the latter is awkward in view of 'happily ever after'. I thought of making Trotter into Fosco Took (Bilbo's first cousin) who vanished when a lad, owing to Gandalf. Who is Trotter? He must have had some bitter acquaintance with Ring-wraiths &c.
From draft to draft, Trotter's personality becomes closer to Aragorn's in the way he speaks and in his knowledge of ancient lore. Only later would Tolkien decide to make him a Man and would decide on his ancestry:
Trotter is a man of Elrond's race descendant of [struck out at once: Turin] the ancient men of the North, and one of Elrond's household. He was a hunter and wanderer. He became a friend of Bilbo. He knew Gandalf. [...] Reason of wooden shoes - no need in this case because Aragorn is a man.
As for the change from Trotter to Strider, it was done very late, but there is not much information on it. I suppose "Trotter" worked for a Hobbit with wooden shoes, but "Strider" was better for a Man with long legs.
There was a major problem with the Ring and Gollum, as originally written in The Hobbit: in the first edition, Gollum wanted to give the Ring as a gift. Tolkien spent a lot of time trying to work around this and come up with reasons why Gollum would want to give up an item which was described as impossible to give up.
It is important to realise that when my father wrote this, he was working within the constraints of the story as originally told in The Hobbit. As The Hobbit first appeared, and until 1951, the story was that Gollum, encountering Bilbo at the edge of the subterranean lake, proposed the riddle game on these conditions: 'If precious asks, and it doesn't answer, we eats it, my preciousss. If it asks us, and we doesn't answer, we gives it a present, gollum!' [...]
This is why, in the present text, Gandalf says 'I think it certain that Gollum knew in the end that Bilbo had got the ring', and why my father had Gandalf develop a theory that Gollum was actually ready to give the ring away: 'he wanted... to hand it on to someone else... I suppose he might have put it in [the goblins'] path in the end... but for the unexpected arrival of Bilbo... as soon as the riddles started a plan formed in his mind.'
This is all carefully conceived in relation to the text of The Hobbit as it then was, to meet the formidable difficulty: if the Ring were of such a nature as my father now conceived it, how could Gollum have really intended to give it away to a stranger who won a riddle contest? - and the original text of The Hobbit left no doubt that that was indeed his serious intention.
It is unclear when he finally decided to change The Hobbit to fit the new story, but the second edition was published in 1951, three years before The Lord of the Rings.
The Evil Treebeard
Treebeard was initially conceived as an evil Giant, in league with the enemy. As Saruman did not exist yet, it was Treebeard who had captured Gandalf:
'Yes!' laughed Gandalf. 'There are many powers greater than mine, for good and evil, in the world. I was caught in Fangorn and spent many weary days as a prisoner of the Giant Treebeard. It was a desperately anxious time, for I was hurrying back to the Shire to help you. I had just learned that the horsemen had been sent out.
Also, in a separate note:
Frodo meets Giant Treebeard in the Forest of Neldoreth while seeking for his lost companions: he is deceived by the giant who pretends to be friendly, but is really in league with the Enemy.
A further outline would change this:
If Treebeard comes in at all - let him be kindly and rather good? About 50 feet high with barky skin. Hair and beard rather like twigs. [...]
Aragorn and Éowyn
In a note marked "to be explained before the end" is this entry:
Aragorn weds Éowyn sister of Éomer (who becomes Lord of Rohan) and becomes King of Gondor.
At this time, Arwen does not exist. I don't think this story was ever expanded because Tolkien decided against it:
Cut out the love-story of Aragorn and Éowyn. Aragorn is too old and lordly and grim. Make Éowyn the twin-sister of Éomund, a stern amazon woman. [...] Probably Éowyn should die to avenge or save Théoden.
The Black Gate and Cirith Ungol
This answer goes into some of the details. In short, Minas Morgul was initially at the Black Gate and this is where Frodo got into Mordor. It would later be moved to Cirith Ungol, some 150 miles south of the Gate.