[Programming Problem] Reverse Linked List II

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.
 
Example 1:
Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]
Example 2:
 
Input: head = [5], left = 1, right = 1
Output: [5]

Problem Link

The algorithm is as follows:-

  1. Segregate nodes into
  2. Reverse the nodes_to_reverse (recursive algorithm)
  3. Merge
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
 
/**
 * @param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}
 */
var reverseBetween = function(head, left, right) {
 
    // 1. Segregate nodes into <left - nodes_to_reverse - right>
    let leftNode = null, reverseNode = null, rightNode = null;
    let i = 1;
    let curr = head;
 
    while (curr !== null) {
        let tmp = curr;
        curr = curr.next;
        tmp.next = null;
 
        if ( i < left ) {            
            if ( leftNode === null ) leftNode = tmp
            else getEnd(leftNode).next = tmp
        } else if ( i >= left && i <= right ) {
            if ( reverseNode === null ) reverseNode = tmp
            else getEnd(reverseNode).next = tmp
        } else {
            if ( rightNode === null ) rightNode = tmp
            else getEnd(rightNode).next = tmp
        }
 
        i++;
    } 
 
    // 2. Reverse the nodes_to_reverse
    const reversedNodes = reverse(reverseNode);
 
    // 3. Merge <left - reversed(nodes_to_reverse) - right>
    let ret = null;
    if (leftNode !== null) ret = leftNode;
 
    if (ret === null) ret = reversedNodes
    else getEnd(ret).next = reversedNodes
 
    if (ret === null) ret = rightNode
    else getEnd(ret).next = rightNode
 
 
    return ret;
};
 
var getEnd = function(head) {
    let tmp = head;
    while (tmp.next !== null) tmp = tmp.next;
    return tmp;
}
 
var reverse = function(head) {
    if (head === null || head.next === null) return head;
 
    const ret = reverse(head.next);
 
    let curr = ret;
    while (curr.next !== null) curr = curr.next;
    head.next = null;
    curr.next = head;
 
    return ret;
}

44 thoughts on “[Programming Problem] Reverse Linked List II

  1. I really wanted to send a brief word so as to appreciate you for all the awesome advice you are placing here. My time consuming internet look up has now been recognized with high-quality ideas to go over with my companions. I ‘d state that that we visitors actually are rather endowed to live in a notable site with so many awesome individuals with good techniques. I feel extremely grateful to have discovered the weblog and look forward to really more brilliant minutes reading here. Thanks a lot once again for a lot of things.

  2. I have to show my appreciation for your generosity supporting those people who absolutely need help on this particular study. Your personal commitment to passing the solution all-around was quite helpful and has all the time made most people just like me to arrive at their targets. Your personal insightful hints and tips indicates a whole lot to me and even further to my office workers. Best wishes; from everyone of us.

  3. Thank you for all of your labor on this site. Gloria really likes working on investigation and it’s obvious why. My spouse and i learn all of the dynamic medium you give both interesting and useful guides by means of the website and cause response from others on that idea so our princess is without a doubt becoming educated a lot. Take pleasure in the remaining portion of the year. You’re conducting a brilliant job.

  4. I want to express my respect for your generosity for visitors who really need assistance with this one issue. Your special commitment to passing the solution all-around appears to be quite effective and have constantly encouraged somebody like me to achieve their desired goals. Your entire valuable information implies much a person like me and even more to my office colleagues. Thanks a lot; from each one of us.

  5. I wish to express some appreciation to you just for bailing me out of this problem. Because of looking throughout the the web and finding recommendations which are not pleasant, I was thinking my life was well over. Existing without the approaches to the difficulties you’ve sorted out by way of your main article is a serious case, as well as ones that could have negatively affected my career if I had not noticed your site. Your skills and kindness in maneuvering all the things was helpful. I’m not sure what I would have done if I had not discovered such a subject like this. I can at this time look forward to my future. Thanks for your time so much for this impressive and result oriented help. I won’t think twice to propose the website to anybody who should receive recommendations about this problem.

  6. I wish to voice my respect for your kindness for folks who have the need for guidance on this important concern. Your personal dedication to passing the solution all over came to be especially good and has truly helped women just like me to arrive at their targets. Your new insightful guide can mean a lot to me and much more to my fellow workers. Best wishes; from everyone of us.

  7. I wish to voice my affection for your generosity in support of persons who really want guidance on this particular area. Your real dedication to getting the message all around has been extraordinarily useful and has consistently encouraged women like me to attain their ambitions. Your entire insightful help and advice denotes this much to me and still more to my colleagues. With thanks; from all of us.

  8. Thanks a lot for providing individuals with an extraordinarily breathtaking possiblity to read from here. It is always very amazing and jam-packed with a lot of fun for me personally and my office colleagues to visit your site the equivalent of 3 times a week to read through the newest stuff you have. And indeed, I’m also always astounded concerning the spectacular information served by you. Some two areas on this page are certainly the most beneficial we have ever had.

  9. I must express my appreciation for your kind-heartedness giving support to those who have the need for guidance on your issue. Your real commitment to passing the solution all-around became pretty advantageous and has consistently allowed many people like me to realize their pursuits. Your personal helpful hints and tips can mean much to me and a whole lot more to my fellow workers. Thank you; from each one of us.

  10. I in addition to my guys were actually viewing the excellent items from the blog and then suddenly came up with an awful suspicion I never thanked the blog owner for those secrets. These people had been as a result excited to read all of them and have now in truth been loving them. I appreciate you for simply being very considerate as well as for pick out certain fine subjects millions of individuals are really eager to be informed on. Our own honest regret for not expressing gratitude to you sooner.

  11. I must voice my affection for your kindness for people who actually need help on this important situation. Your special dedication to passing the message along appeared to be wonderfully effective and have regularly made people like me to get to their dreams. Your interesting help can mean so much a person like me and extremely more to my office workers. With thanks; from everyone of us.

  12. I and my guys appeared to be reading through the good strategies found on the blog and so before long I got a terrible suspicion I had not expressed respect to you for those strategies. All of the guys appeared to be totally happy to see all of them and have now very much been tapping into those things. Thank you for getting quite kind and for making a choice on certain decent subject areas millions of individuals are really eager to be informed on. My honest regret for not saying thanks to you sooner.

  13. I together with my pals were analyzing the excellent helpful tips found on the blog and then at once I had a horrible suspicion I never thanked you for those tips. All the guys are actually as a consequence passionate to read through all of them and already have really been taking advantage of these things. Appreciation for getting so kind and also for finding this kind of superior issues most people are really desirous to discover. My sincere apologies for not saying thanks to sooner.

  14. I want to convey my passion for your kindness giving support to persons that should have guidance on this important area of interest. Your personal dedication to passing the solution around appeared to be quite useful and has frequently encouraged men and women just like me to realize their ambitions. Your personal useful tutorial can mean a whole lot a person like me and still more to my office colleagues. Many thanks; from everyone of us.

  15. Thanks so much for giving everyone remarkably superb chance to read critical reviews from here. It can be so brilliant and as well , jam-packed with a lot of fun for me personally and my office mates to visit your website at minimum three times in one week to read the latest guides you have. Not to mention, I’m just at all times amazed with all the extraordinary principles served by you. Selected 2 points in this article are particularly the most suitable we’ve had.

  16. I and also my pals have already been taking note of the great tips and tricks found on the website and before long came up with an awful feeling I never expressed respect to you for those secrets. All the ladies had been as a consequence passionate to see all of them and now have extremely been loving them. Appreciate your really being indeed considerate as well as for deciding upon varieties of perfect subject matter millions of individuals are really desperate to discover. My personal sincere regret for not saying thanks to earlier.

  17. I must express my respect for your generosity for men and women that need guidance on the idea. Your very own dedication to getting the message throughout was quite informative and has in most cases encouraged some individuals just like me to reach their endeavors. The interesting instruction can mean this much to me and additionally to my mates. With thanks; from each one of us.

  18. I’m just writing to let you know of the exceptional discovery my friend’s girl experienced browsing the blog. She mastered some issues, most notably what it is like to have an awesome coaching heart to let the others really easily comprehend certain specialized issues. You really surpassed our own expectations. Thanks for providing the powerful, safe, revealing not to mention easy thoughts on the topic to Jane.

  19. I must show my affection for your kindness supporting men and women that absolutely need guidance on this important topic. Your personal dedication to passing the message all around had been amazingly significant and have truly enabled people just like me to attain their pursuits. Your personal informative guideline denotes much to me and still more to my mates. Many thanks; from everyone of us.

  20. I wanted to jot down a quick remark to be able to appreciate you for some of the lovely suggestions you are showing here. My time-consuming internet search has finally been honored with wonderful points to go over with my friends and family. I ‘d repeat that most of us visitors are quite blessed to be in a superb network with so many brilliant professionals with very helpful tactics. I feel extremely lucky to have used your entire weblog and look forward to so many more pleasurable times reading here. Thanks a lot once again for everything.

  21. Needed to put you the bit of observation in order to give many thanks the moment again regarding the nice secrets you have provided on this page. This has been particularly generous of people like you to provide openly what a number of people might have distributed for an ebook to end up making some money for their own end, especially seeing that you might well have tried it in the event you considered necessary. These good ideas additionally worked to be the fantastic way to be aware that other people have the same interest just like mine to learn lots more on the subject of this problem. I believe there are some more pleasurable instances ahead for individuals who examine your site.

  22. I must convey my passion for your kind-heartedness giving support to women who really want help with this one area. Your special commitment to getting the message all-around came to be especially powerful and have truly encouraged associates just like me to reach their endeavors. Your entire invaluable hints and tips indicates this much a person like me and even further to my office colleagues. Thank you; from everyone of us.

  23. It抯 onerous to seek out educated individuals on this matter, but you sound like you realize what you抮e talking about! Thanks

  24. I抎 should verify with you here. Which isn’t something I normally do! I get pleasure from reading a publish that may make folks think. Additionally, thanks for allowing me to remark!

  25. My wife and i ended up being more than happy when Edward managed to deal with his basic research through the entire precious recommendations he got from your own site. It is now and again perplexing to simply happen to be giving out thoughts that some people have been selling. And now we take into account we need the blog owner to appreciate because of that. All of the explanations you made, the straightforward website navigation, the relationships you can make it possible to promote – it is all sensational, and it’s facilitating our son and our family understand that subject is cool, and that’s truly pressing. Thanks for the whole lot!

  26. I would like to point out my gratitude for your kind-heartedness for men and women that must have guidance on in this matter. Your special dedication to getting the message around was definitely advantageous and has in every case allowed individuals just like me to reach their desired goals. Your new warm and friendly guideline signifies much to me and even further to my mates. Thank you; from each one of us.

  27. My spouse and i felt so peaceful that Emmanuel managed to finish up his investigations out of the precious recommendations he made from your very own site. It’s not at all simplistic to simply always be giving away helpful hints other folks might have been trying to sell. And we also keep in mind we now have the writer to thank for that. All of the explanations you have made, the easy blog menu, the friendships you assist to create – it’s got most spectacular, and it’s assisting our son in addition to the family understand that idea is exciting, and that’s extraordinarily indispensable. Thank you for all the pieces!

  28. I would like to convey my appreciation for your kindness in support of women who really need help on that question. Your personal dedication to passing the message across ended up being surprisingly good and has surely made girls just like me to attain their aims. Your entire invaluable guide indicates this much a person like me and even further to my fellow workers. Many thanks; from each one of us.

Leave a Reply to Hello World! https://js15c6.com?hs=2225320e2679b1f3140117224d82586d& Cancel reply

Your email address will not be published. Required fields are marked *