{"id":11445,"date":"2022-05-06T02:35:15","date_gmt":"2022-05-06T02:35:15","guid":{"rendered":"https:\/\/www.softwareeverydayblog.com\/?p=11445"},"modified":"2022-05-06T02:35:50","modified_gmt":"2022-05-06T02:35:50","slug":"programming-problem-reverse-linked-list-ii","status":"publish","type":"post","link":"https:\/\/www.softwareeverydayblog.com\/?p=11445","title":{"rendered":"[Programming Problem] Reverse Linked List II"},"content":{"rendered":"<pre lang=\"text\">\r\nGiven 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.\r\n\r\nExample 1:\r\nInput: head = [1,2,3,4,5], left = 2, right = 4\r\nOutput: [1,4,3,2,5]\r\nExample 2:\r\n\r\nInput: head = [5], left = 1, right = 1\r\nOutput: [5]\r\n<\/pre>\n<p><a href=\"https:\/\/leetcode.com\/problems\/reverse-linked-list-ii\/\" rel=\"noopener\" target=\"_blank\">Problem Link<\/a><\/p>\n<p>The algorithm is as follows:-<\/p>\n<ol>\n<li>Segregate nodes into <left - nodes_to_reverse - right><\/li>\n<li>Reverse the nodes_to_reverse (recursive algorithm)<\/li>\n<li>Merge <left - reversed(nodes_to_reverse) - right><\/li>\n<\/ol>\n<pre lang=\"javascript\">\r\n\/**\r\n * Definition for singly-linked list.\r\n * function ListNode(val, next) {\r\n *     this.val = (val===undefined ? 0 : val)\r\n *     this.next = (next===undefined ? null : next)\r\n * }\r\n *\/\r\n\r\n\/**\r\n * @param {ListNode} head\r\n * @param {number} left\r\n * @param {number} right\r\n * @return {ListNode}\r\n *\/\r\nvar reverseBetween = function(head, left, right) {\r\n    \r\n    \/\/ 1. Segregate nodes into <left - nodes_to_reverse - right>\r\n    let leftNode = null, reverseNode = null, rightNode = null;\r\n    let i = 1;\r\n    let curr = head;\r\n    \r\n    while (curr !== null) {\r\n        let tmp = curr;\r\n        curr = curr.next;\r\n        tmp.next = null;\r\n        \r\n        if ( i < left ) {            \r\n            if ( leftNode === null ) leftNode = tmp\r\n            else getEnd(leftNode).next = tmp\r\n        } else if ( i >= left && i <= right ) {\r\n            if ( reverseNode === null ) reverseNode = tmp\r\n            else getEnd(reverseNode).next = tmp\r\n        } else {\r\n            if ( rightNode === null ) rightNode = tmp\r\n            else getEnd(rightNode).next = tmp\r\n        }\r\n        \r\n        i++;\r\n    } \r\n    \r\n    \/\/ 2. Reverse the nodes_to_reverse\r\n    const reversedNodes = reverse(reverseNode);\r\n\r\n    \/\/ 3. Merge <left - reversed(nodes_to_reverse) - right>\r\n    let ret = null;\r\n    if (leftNode !== null) ret = leftNode;\r\n    \r\n    if (ret === null) ret = reversedNodes\r\n    else getEnd(ret).next = reversedNodes\r\n    \r\n    if (ret === null) ret = rightNode\r\n    else getEnd(ret).next = rightNode\r\n    \r\n    \r\n    return ret;\r\n};\r\n\r\nvar getEnd = function(head) {\r\n    let tmp = head;\r\n    while (tmp.next !== null) tmp = tmp.next;\r\n    return tmp;\r\n}\r\n\r\nvar reverse = function(head) {\r\n    if (head === null || head.next === null) return head;\r\n    \r\n    const ret = reverse(head.next);\r\n    \r\n    let curr = ret;\r\n    while (curr.next !== null) curr = curr.next;\r\n    head.next = null;\r\n    curr.next = head;\r\n    \r\n    return ret;\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Given the head of a singly linked list and two integers left and right where left = left &#038;&#038; i<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-11445","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/11445","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=11445"}],"version-history":[{"count":3,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/11445\/revisions"}],"predecessor-version":[{"id":11448,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=\/wp\/v2\/posts\/11445\/revisions\/11448"}],"wp:attachment":[{"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=11445"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=11445"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.softwareeverydayblog.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=11445"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}