When you first get out of college you can write a 500 line program, and you get dropped you into a million line program. You get assigned a senior engineer to help you over the hump this takes a few years while you learn things that "everybody knows" but are not taught in school. Hopefully you get the first part of this over as an intern, but there is still more to learn.
Once you get over that hump you can do okay on your own. You can be assigned to write code and you rarely need help (you will always need help, but this point not often). You are still learning, but overall you get things done.
Senior engineer is you have been around for a enough years for a few of the following. Different companies value different things, and I've surely forgot something. I know engineers who never made the senior level because they refused to do something on this list even though if forced they were proven to do well.
You start to teach the other junior engineers how to be better engineers.
You start to see the larger picture of the whole system and how it should be changed for the better.
You start to see how the work individual developers do fits together and get involved with planning on how it is done (breakdown and ordering) so that the project finishes on time.
You become a specialist in something that is important to your company. This can be company specific, or a generic skill that applies elsewhere. (note that if the company doesn't realize how important the area is you won't be rewarded - preventing a problem the company never knew they had won't help)
Mozilla engineer leveling chart is a good example. There are probably other companies that expose the criteria they use as well.
I recent left a level 5 of 7 job for a title level 2 of 6 and still managed a 30% pay raise. On paper, it looks like a huge step back (Consulting Data Scientist to Software Engineer), but in practice, it's actually more of a technical leadership role.
The other possibility is that they have seen the problem before, fixed it, but didn't know it was called "calculating the Big-O bullshit of reversing linked lists while merge sorting"...
I have 25+ years of experience; in a month I will turn 46. I don't have a CS degree, nor even a BS. I'm one of those devs who started basically fresh out of high school, and made a career out of it. I'm not even sure that is possible to do any longer.
What I don't have is all of that CS knowledge and terminology. That isn't to say that I could solve all of those problems, or that I have encountered them, or come up with the correct or practical solutions. To be fair, I am always learning something new (and I like it that way). Also, to the "example" you give, I'd have to look up how to reverse a linked list and what a merge sort exactly was. Hopefully, there's some kind of standard library for both in the language I was using, but if I had to do it from scratch, right now off the top of my head, I couldn't do it.
But I would know how to figure out and ask the right questions on how to do it, and go from there.
And that's really one of the best skills as a developer to have, imho. There have been times where I have had a problem, tried to google for it - thinking it was a common issue - found that it was a common issue, with people asking the questions - but either no solutions, or worse:
...and so, by breaking the problem down, figuring out the answer to those questions (with either more googling, or implementing a custom solution), then pulling all those parts back into one coherent answer for the initial problem - that greater issue can be solved.
Then I find a forum or something and post the solution there, so that future coders can at least have one good reference point, for as long as the forum exists. Nowadays, I'd probably put it on my github repo or something.
Ultimately - there are a lot of "senior devs" (both in age and ability) who are currently in my place; people who didn't go the tradition educational route; people who were coding in their bedrooms on 8-bit home computers in assembler and BASIC because that's all we had at the time. We may or may not have run across those CS-level problems. If we did, we didn't know their names (much like not knowing the names for certain "patterns" - yet another similar thing) - but we still may have implemented solutions for them anyhow.
I have faith in your problem solving abilities. I'm 35 and have a CS degree. The only time I've needed to know Big-O or how sorting algos worked was in college and during interviews. I've literally never been in a situation where the code functionally worked, but ran too slowly because of an inefficient algorithm (and this is with 13 years as a C++ developer).
As for your situation, I suspect many shops would turn you down because you didn't rattle back the answer from memory. But the concern isn't that you aren't smart enough, it's that you're "old" and cost too much. The kid who memorized leetcode can be bought cheaply and discarded easily if it comes to light that he/she can't figure out how to solve a tech bug. If you "follow the money", these interviews could be seen as purely "cheap-but-comptetent people-filters". Because if an old programmer tried to sue them for age discrimination, they could point to leetcode as evidence that all the tests were administered "fairly".
1) Junior Engineer - can write basic code, but usually needs help for bigger projects or navigating a code base.
2) Engineer - Is pretty independent and can whip together what they need based on a design.
3) Senior Engineer - Can take a problem and build a design for it, can lead a team of lower-level engineers to properly implement the design.
There are higher levels like staff and principal engineer, these ones typically are the same as senior engineers but are at larger scopes.
At levels 3 and higher, you tend to write more English than code. You're there to decide what code gets written, rather than the specifics on how it gets written. That's what levels 1 and 2 do, they'll take your designs and implement them.