Leetcode-206 Reverse Linked List Difficulty: Easy
Given the head of a singly linked list, reverse the list, and return the reversed list.
Example 1:
Input: head = [1,2,3,4,5] Output: [5,4,3,2,1]
Example 2:
Input: head = [1,2] Output: [2,1]
Example 3:
Input: head = [] Output: []
Constraints:
- The number of nodes in the list is the range
[0, 5000]. -5000 <= Node.val <= 5000
Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?
ALERT, ALERT, ALERT !!!
If you have come to see the solution before trying to solve it yourself, this really won’t help you, promise! If that is the case, we will recommend, please go back and first try it yourself. If you can’t solve it after (at least)an hour of thinking and trying, please come back! 🙂You can solve it here
__________________________________________________________
Recursive Solution
Let’s consider we have a linked list like below. A single node of list has 1) a value part and 2) a pointer that points to the next element.
A separate head pointer points to node A, next pointer of A points to B and so on. Finally, D is the last element of list, so, it points to NULL. After the list is reversed, D will be the first element and A will be the last element.
The idea of recursive solution is, we will traverse forward from A to D, then will return D and traverse backward to A. During the backward traversal, we will change each pointer’s direction so that they point to their respective previous element. For example, D will point to C, C will point to B and so on. Finally, being the last element, node A of the reversed list will point to NULL. So, let’s see how the recursive algorithm will work as we traverse forward and then backward.
Forward Traversal
The above image shows how forward traversal will look like for each step from A to D. Each recursion call creates a stack frame for the local variables. So, in step-1, A will be stored in stack, then B in step-2, then C and so on. Finally, D points to NULL, so there will be no more recursive calls. Instead, D will be returned. In the code, this is like:
if (head->next == NULL) return head; // in case of D, head = D
Backward Traversal
Returned value of D will be received by C. For that, we will use a variable named tail. From C, this will be returned to B. So, ultimately C is returning D to B. Similarly, B will return D to A, and finally A will also return D to the caller of recursive function. This way, we will receive D as the head of the reversed linked list.
Now, for each node, before returning D to it’s previous node, some magic will happen! Let’s take C for example. Before returning D to B (using tail variable), C will make D to point back to C. Formally, we need to do C->next->next = C and then C->next = NULL. In code, this is like:
head->next->next = head; head->next = NULL;
Let’s see how the backward traversal will work visually.
Backward Traverse – D to C
Backward Traverse – C to B
Backward Traverse – B to A
Final List
Code
class Solution {
public:
ListNode* rec(ListNode* head) {
if(head->next == NULL)
return head;
ListNode* tail = rec(head->next);
head->next->next = head;
head->next = NULL;
return tail;
}
ListNode* reverseList(ListNode* head) {
if(head == NULL) return head;
return rec(head);
}
};Thanks for reading. Please let us know if any part of this tutorial is hard to understand. Comment if you like it, hate it or want to suggest for improvement.
Happy Coding ! 😀
This site is really a walk-by means of for all of the data you needed about this and didn’t know who to ask. Glimpse here, and also you’ll undoubtedly uncover it.
I was wondering if you ever considered changing the page layout of your blog? Its very well written; I love what youve got to say. But maybe you could a little more in the way of content so people could connect with it better. Youve got an awful lot of text for only having 1 or 2 images. Maybe you could space it out better?
Great topic, please keep it up I really enjoy reading these type articles.
Apoiar ferramentas de apostas e estar equipado com uma plataforma diversificada de transações financeiras, a 20Bet oferece suporte tangível aos jogadores. Este é um lugar onde eles podem apostar com dinheiro real, respaldados por concorrentes de diversas disciplinas esportivas. 20bet
Your article gave me a lot of inspiration, I hope you can explain your point of view in more detail, because I have some doubts, thank you. 20bet
Hello foolishhungry.com administrator, Your posts are always a great source of information.
Dear foolishhungry.com administrator, Thanks for sharing your thoughts!
Hello foolishhungry.com webmaster, Your posts are always well-received and appreciated.
Hi foolishhungry.com administrator, Thanks for the well-researched and well-written post!
Hello foolishhungry.com administrator, Your posts are always well-supported by facts and figures.
Dear foolishhungry.com admin, Keep up the great work!
Hello foolishhungry.com admin, Thanks for the well-researched and well-written post!
I’m captivated by your talent to turn mundane topics into captivating writing. Kudos!
To the foolishhungry.com admin, Your posts are always on topic and relevant.
Thank you very much for sharing, I learned a lot from your article. Very cool. Thanks. nimabi
Very great information can be found on blog.
It’s really a nice and useful piece of information. I’m glad that you shared this helpful info with us. Please keep us informed like this. Thank you for sharing.
I think you have remarked some very interesting details, appreciate it for the post.
Dear foolishhungry.com owner, Good work!
Hello! Someone in my Myspace group shared this website with us so I came to take a look. I’m definitely loving the information. I’m bookmarking and will be tweeting this to my followers! Excellent blog and terrific design and style.
good post.Never knew this, thanks for letting me know.
Dear foolishhungry.com administrator, You always provide great examples and case studies.
Your article helped me a lot, is there any more related content? Thanks! https://accounts.binance.com/it/register?ref=53551167
Hi foolishhungry.com webmaster, You always provide in-depth analysis and understanding.
Can you be more specific about the content of your article? After reading it, I still have some doubts. Hope you can help me. https://www.binance.com/ur/join?ref=OMM3XK51
Thanks for sharing. I read many of your blog posts, cool, your blog is very good. https://www.binance.info/lv/join?ref=V3MG69RO
Thanks for sharing. I read many of your blog posts, cool, your blog is very good. https://www.binance.info/zh-TC/join?ref=DB40ITMB
I don’t think the title of your article matches the content lol. Just kidding, mainly because I had some doubts after reading the article. https://www.binance.com/ph/register?ref=S5H7X3LP
Can you be more specific about the content of your article? After reading it, I still have some doubts. Hope you can help me. https://accounts.binance.com/zh-TC/register-person?ref=YY80CKRN
Thanks for sharing. I read many of your blog posts, cool, your blog is very good. https://accounts.binance.com/ru/register?ref=W0BCQMF1
I’ve been exploring for a little bit for any high-quality articles or weblog posts on this sort of space . Exploring in Yahoo I at last stumbled upon this site. Studying this info So i am satisfied to express that I’ve an incredibly just right uncanny feeling I came upon just what I needed. I such a lot indubitably will make certain to don’t omit this website and give it a look on a continuing basis.
An interesting dialogue is value comment. I feel that it’s best to write more on this topic, it may not be a taboo topic however typically individuals are not enough to speak on such topics. To the next. Cheers
Thank you for your sharing. I am worried that I lack creative ideas. It is your article that makes me full of hope. Thank you. But, I have a question, can you help me?
Can you be more specific about the content of your article? After reading it, I still have some doubts. Hope you can help me.
Hello. excellent job. I did not anticipate this. This is a splendid story. Thanks!
Can you be more specific about the content of your article? After reading it, I still have some doubts. Hope you can help me.
Great write-up, I’m normal visitor of one’s site, maintain up the nice operate, and It’s going to be a regular visitor for a lengthy time.
Your point of view caught my eye and was very interesting. Thanks. I have a question for you.
What Is Sugar Defender? Sugar Defender is a natural blood sugar support formula created by Tom Green. It is based on scientific breakthroughs and clinical studies.
naturally like your web site however you have to test the spelling on several of your posts. Several of them are rife with spelling issues and I in finding it very bothersome to inform the truth however I¦ll definitely come back again.
Terrific post however I was wanting to know if you could write a litte more on this topic? I’d be very thankful if you could elaborate a little bit further. Thanks!
I am thankful that I observed this weblog, exactly the right information that I was looking for! .
Keep working ,splendid job!
Thanks for the sensible critique. Me and my neighbor were just preparing to do a little research about this. We got a grab a book from our area library but I think I learned more from this post. I am very glad to see such excellent information being shared freely out there.
What i do not realize is actually how you are not actually much more well-liked than you might be right now. You are very intelligent. You realize thus considerably relating to this subject, produced me personally consider it from numerous varied angles. Its like men and women aren’t fascinated unless it’s one thing to do with Lady gaga! Your own stuffs outstanding. Always maintain it up!
I want to express my appreciation to this writer for bailing me out of this problem. As a result of scouting through the online world and coming across principles that were not helpful, I figured my life was over. Living minus the approaches to the problems you’ve sorted out as a result of your main review is a serious case, and those that might have in a negative way affected my entire career if I had not noticed your web site. Your actual capability and kindness in dealing with almost everything was valuable. I don’t know what I would’ve done if I hadn’t encountered such a point like this. It’s possible to at this time look forward to my future. Thanks for your time very much for this reliable and effective help. I won’t hesitate to suggest the sites to any individual who wants and needs assistance about this issue.
Hi foolishhungry.com admin, You always provide great examples and real-world applications.
whoah this blog is fantastic i love reading your articles. Keep up the great work! You know, a lot of people are hunting around for this info, you can aid them greatly.
Well I sincerely liked studying it. This post offered by you is very helpful for good planning.