{"id":4888,"date":"2021-09-13T02:35:28","date_gmt":"2021-09-13T02:35:28","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=4888"},"modified":"2022-12-13T12:04:59","modified_gmt":"2022-12-13T12:04:59","slug":"rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/","title":{"rendered":"Rearrange the given linked list such that it consists of alternating minimum-maximum elements"},"content":{"rendered":"<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000410738-Article_130.png\" alt=\"\" \/><\/p>\n<p>This article taught you the most interesting and efficient problem of the linked list \u201cRearrange linked list in alternate last and first\u201d. We will see the approach, algorithms, dry run, and code implementation. We hope this article will enhance your knowledge of the linked list. Let us understand the problem statement of Rearrange linked list in alternate last and first for a better understanding.<\/p>\n<h2>How to Rearrange linked list in alternate last and first<\/h2>\n<p>In this problem, we are given a LinkedList (root node) and we are asked to rearrange it such that after rearrangement, it will contain alternating minimum and maximum elements in the following format:<\/p>\n<ul>\n<li>The first element should be the minimum element. <\/li>\n<li>The second element should be the maximum element. <\/li>\n<li>The third element should be the next minimum and the fourth element should be the next maximum and so on.<\/li>\n<\/ul>\n<p>Let\u2019s see an example:<br \/>\n<strong>Input<\/strong>:<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/input-6.png\" alt=\"\" \/><\/p>\n<p><strong>Output<\/strong>:<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/output-5.png\" alt=\"\" \/><\/p>\n<p>Let\u2019s first understand the problem statement with the help of examples.<\/p>\n<p>If the given linked list is: head \u219212 \u2192 4 \u2192 5 \u2192 9 \u2192 10 \u2192 6.<br \/>\nWe can form our output list having alternating minimum-maximum elements following the below steps.<\/p>\n<ul>\n<li>\n<p>As 4 is the minimum element so, it will be the first element in the resultant list.<\/p>\n<ul>\n<li>Resultant list after this step: head \u21924 <\/li>\n<\/ul>\n<\/li>\n<li>\n<p>12 is the maximum element so, it will be the second element in the resultant list.<\/p>\n<ul>\n<li>Resultant list after this step: head \u21924 \u2192 12<\/li>\n<\/ul>\n<\/li>\n<li>\n<p>5 is the next minimum after 4 so, it is the third element. <\/p>\n<ul>\n<li>Resultant list after this step: head \u21924 \u2192 12 \u2192 5 <\/li>\n<\/ul>\n<\/li>\n<li>\n<p>10 is the next maximum after 12 so, it is the fourth element. <\/p>\n<ul>\n<li>Resultant list after this step: head \u21924 \u2192 12 \u2192 5 \u2192 10 <\/li>\n<\/ul>\n<\/li>\n<li>\n<p>6 is the next minimum after 5 so, it is the fifth element. <\/p>\n<ul>\n<li>Resultant list after this step: head \u21924 \u2192 12 \u2192 5 \u2192 10 \u2192 6 <\/li>\n<\/ul>\n<\/li>\n<li>\n<p>9 is the next maximum after 10 so, it is the sixth element.<\/p>\n<ul>\n<li>Resultant list after this step: head \u21924 \u2192 12 \u2192 5 \u2192 10 \u2192 6 \u2192 9<\/li>\n<\/ul>\n<\/li>\n<li>\n<p>Our final resultant linked list having alternating minimum-maximum elements will be: head \u21924 \u2192 12 \u2192 5 \u2192 10 \u2192 6 \u2192 9<\/p>\n<\/li>\n<\/ul>\n<p>Now I think from the above examples, the problem statement is clear. So let&#8217;s see how we will approach it. Any Ideas?<\/p>\n<ul>\n<li>If not, it&#8217;s okay. We will see in the next section some helpful observations using which we will try to devise our algorithm.<\/li>\n<\/ul>\n<p>Let\u2019s move to the next section.<\/p>\n<p><strong>Helpful Observations of Rearrange linked list in alternate last and first<\/strong><\/p>\n<ol>\n<li>\n<p>If we sort the given list we get:<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/Rearrange-the-given-linked-list-such-that-it-consists-of-alternating-elements-1.png\" alt=\"\" \/><\/p>\n<\/li>\n<li>\n<p>If we reverse the sorted list after the middle element we get:<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/Rearrange-the-given-linked-list-such-that-it-consists-of-alternating-elements-2.png\" alt=\"\" \/><\/p>\n<\/li>\n<li>\n<p>The first half of the linked list from observation 2, which contains linked list sorted in ascending order.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/Rearrange-the-given-linked-list-such-that-it-consists-of-alternating-elements-3.png\" alt=\"\" \/><\/p>\n<\/li>\n<li>\n<p>The second half of the linked list from observation 2, which contains linked list sorted in descending order.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/Rearrange-the-given-linked-list-such-that-it-consists-of-alternating-elements-4.png\" alt=\"\" \/><\/p>\n<\/li>\n<\/ol>\n<p>Here, on careful observation we can see that our resultant list head \u21924 \u2192 12 \u2192 5 \u2192 10 \u2192 6 \u2192 9 is nothing but just a combination of the alternate nodes from the two lists in observations 3 and 4. So, we will use this observation to create our algorithm.<\/p>\n<h2>Approach and Algorithm of Rearrange linked list in alternate last and first<\/h2>\n<ul>\n<li>Sort the given list. Here, we will be using merge sort to sort the given list. You can sort the list using any sorting method you like. <\/li>\n<li>Get the middle element using the tortoise and hare approach. The tortoise and hare approach is an efficient way to find the middle element of a list.<\/li>\n<li>Reverse the list after the middle element and store it as a separate list.<\/li>\n<li>Create a new empty list pointed by the result pointer.<\/li>\n<li>Alternatively, add elements from the firstList and the reversedList starting with the firstList as we have to add in minimum and maximum order.<\/li>\n<li>After adding all the elements from the firstList and the reversedList into the list pointed by the result. The result will contain the required list having alternating minimum-maximum elements.<\/li>\n<\/ul>\n<h3>Dry Run of Rearrange linked list in alternate last and first<\/h3>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/Rearrange-the-given-linked-list-such-that-it-consists-of-alternating-elements-5.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/Rearrange-the-given-linked-list-such-that-it-consists-of-alternating-elements-6.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/Rearrange-the-given-linked-list-such-that-it-consists-of-alternating-elements-7.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/09\/Rearrange-the-given-linked-list-such-that-it-consists-of-alternating-elements-8.png\" alt=\"\" \/><\/p>\n<h2>Code Implementation of Rearrange linked list in alternate last and first<\/h2>\n\t\t\t\t\t\t<style>\r\n\t\t\t\t\r\n\t\t\t\t\t#tab_container_4890 {\r\n\toverflow:hidden;\r\n\tdisplay:block;\r\n\twidth:100%;\r\n\tborder:0px solid #ddd;\r\n\tmargin-bottom:30px;\r\n\t}\r\n\r\n#tab_container_4890 .tab-content{\r\n\tpadding:20px;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n\tmargin-top: 0px;\r\n\tbackground-color:#ffffff !important;\r\n\tcolor: #000000 !important;\r\n\tfont-size:16px !important;\r\n\tfont-family: Open Sans !important;\r\n\t\r\n\t\tborder: 1px solid #e6e6e6 !important;\r\n\t}\r\n#tab_container_4890 .wpsm_nav-tabs {\r\n    border-bottom: 0px solid #ddd;\r\n}\r\n#tab_container_4890 .wpsm_nav-tabs > li.active > a, #tab_container_4890 .wpsm_nav-tabs > li.active > a:hover, #tab_container_4890 .wpsm_nav-tabs > li.active > a:focus {\r\n\tcolor: #000000 !important;\r\n\tcursor: default;\r\n\tbackground-color: #ffffff !important;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n}\r\n\r\n#tab_container_4890 .wpsm_nav-tabs > li > a {\r\n    margin-right: 0px !important; \r\n    line-height: 1.42857143 !important;\r\n    border: 1px solid #d5d5d5 !important;\r\n    border-radius: 0px 0px 0 0 !important; \r\n\tbackground-color: #e8e8e8 !important;\r\n\tcolor: #000000 !important;\r\n\tpadding: 15px 18px 15px 18px !important;\r\n\ttext-decoration: none !important;\r\n\tfont-size: 14px !important;\r\n\ttext-align:center !important;\r\n\tfont-family: Open Sans !important;\r\n}\r\n#tab_container_4890 .wpsm_nav-tabs > li > a:focus {\r\noutline: 0px !important;\r\n}\r\n\r\n#tab_container_4890 .wpsm_nav-tabs > li > a:before {\r\n\tdisplay:none !important;\r\n}\r\n#tab_container_4890 .wpsm_nav-tabs > li > a:after {\r\n\tdisplay:none !important ;\r\n}\r\n#tab_container_4890 .wpsm_nav-tabs > li{\r\npadding:0px !important ;\r\nmargin:0px;\r\n}\r\n\r\n#tab_container_4890 .wpsm_nav-tabs > li > a:hover , #tab_container_4890 .wpsm_nav-tabs > li > a:focus {\r\n    color: #000000 !important;\r\n    background-color: #e8e8e8 !important;\r\n\tborder: 1px solid #d5d5d5 !important;\r\n\t\r\n}\r\n#tab_container_4890 .wpsm_nav-tabs > li > a .fa{\r\n\r\nmargin-right:5px !important;\r\n\r\nmargin-left:5px !important;\r\n\r\n\r\n}\r\n\r\n\t\t#tab_container_4890 .wpsm_nav-tabs a{\r\n\t\t\tbackground-image: none;\r\n\t\t\tbackground-position: 0 0;\r\n\t\t\tbackground-repeat: repeat-x;\r\n\t\t}\r\n\t\t\t\r\n\r\n\r\n#tab_container_4890 .wpsm_nav-tabs > li {\r\n    float: left;\r\n    margin-bottom: -1px !important;\r\n\tmargin-right:0px !important; \r\n}\r\n\r\n\r\n#tab_container_4890 .tab-content{\r\noverflow:hidden !important;\r\n}\r\n\r\n\r\n@media (min-width: 769px) {\r\n\r\n\t#tab_container_4890 .wpsm_nav-tabs > li{\r\n\t\tfloat:left !important ;\r\n\t\t\t\tmargin-right:-1px !important;\r\n\t\t\t\t\t}\r\n\t#tab_container_4890 .wpsm_nav-tabs{\r\n\t\tfloat:none !important;\r\n\t\tmargin:0px !important;\r\n\t}\r\n\r\n\t#tab_container_4890 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_4890 .wpsm_nav{\r\n\t\t\t}\r\n\r\n}\r\n\r\n\r\n\r\n@media (max-width: 768px) {\r\n\t#tab_container_4890 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_4890 .wpsm_nav{\r\n\t\t\t}\r\n}\r\n\r\n\r\n\t.wpsm_nav-tabs li:before{\r\n\t\tdisplay:none !important;\r\n\t}\r\n\r\n\t@media (max-width: 768px) {\r\n\t\t\t\t\r\n\t\t\t\t.wpsm_nav-tabs{\r\n\t\t\tmargin-left:0px !important;\r\n\t\t\tmargin-right:0px !important; \r\n\t\t\t\r\n\t\t}\r\n\t\t\t\t#tab_container_4890 .wpsm_nav-tabs > li{\r\n\t\t\tfloat:none !important;\r\n\t\t}\r\n\t\t\t\r\n\t}\t\t\t\t<\/style>\r\n\t\t\t\t<div id=\"tab_container_4890\" >\r\n\t \r\n\t\t\t\t\t<ul class=\"wpsm_nav wpsm_nav-tabs\" role=\"tablist\" id=\"myTab_4890\">\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  class=\"active\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_4890_1\" aria-controls=\"tabs_desc_4890_1\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>Java<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_4890_2\" aria-controls=\"tabs_desc_4890_2\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>Python<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\t\t\t\t <\/ul>\r\n\r\n\t\t\t\t\t  <!-- Tab panes -->\r\n\t\t\t\t\t  <div class=\"tab-content\" id=\"tab-content_4890\">\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane  in active \" id=\"tabs_desc_4890_1\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"java\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\npublic class Prepbytes {\r\n    static class Node {\r\n        int data;\r\n        Node next;\r\n\r\n        Node() {\r\n        };\r\n\r\n        Node(int num) {\r\n            data = num;\r\n            next = null;\r\n        }\r\n    };\r\n\r\n    public static Node rearrangeListToHaveMinMaxElements(Node head) {\r\n        if (head == null) {\r\n            return head;\r\n        }\r\n \t   if (head.next == null) {\r\n            return head;\r\n        }\r\n\r\n        head = getSortedList(head);\r\n\r\n        Node mid = getMidNode(head);\r\n        Node secondList = mid.next;\r\n        mid.next = null;\r\n\r\n        Node reversedList = getReversedList(secondList);\r\n        Node firstList = head;\r\n\r\n        Node result = new Node();\r\n        Node node = result;\r\n\r\n        while (firstList != null || reversedList != null) {\r\n\r\n            if (firstList != null) {\r\n                node.next = firstList;\r\n                node = node.next;\r\n                firstList = firstList.next;\r\n            }\r\n\r\n            if (reversedList != null) {\r\n                node.next = reversedList;\r\n                node = node.next;\r\n                reversedList = reversedList.next;\r\n            }\r\n        }\r\n\r\n        return result.next;\r\n    }\r\n\r\n    public static Node getSortedList(Node node) {\r\n        if (node == null || node.next == null) {\r\n            return node;\r\n        }\r\n\r\n        Node mid = getMidNode(node);\r\n        Node next = mid.next;\r\n        mid.next = null;\r\n\r\n        Node lista = getSortedList(node);\r\n        Node listb = getSortedList(next);\r\n\r\n        return merge(lista, listb);\r\n    }\r\n\r\n    public static Node merge(Node lista, Node listb) {\r\n        if (lista == null &amp;&amp; listb == null) {\r\n            return null;\r\n        }\r\n\r\n        Node temp = new Node();\r\n        Node mergedList = temp;\r\n        \r\n        while (lista != null &amp;&amp; listb != null) {\r\n            \r\n            if (lista.data &lt; listb.data) {\r\n                temp.next = lista;\r\n                lista = lista.next;\r\n            } else {\r\n                temp.next = listb;\r\n                listb = listb.next;\r\n            }\r\n\r\n            temp = temp.next;\r\n        }\r\n        if (lista != null) {\r\n            temp.next = lista;\r\n        } \r\n   else {\r\n            temp.next = listb;\r\n        }\r\n\r\n        return mergedList.next;\r\n    }\r\n\r\n    public static Node getMidNode(Node node) {\r\n        Node slow = node;\r\n        Node fast = node;\r\n        while (fast.next != null &amp;&amp; fast.next.next != null) {\r\n            slow = slow.next;\r\n            fast = fast.next.next;\r\n        }\r\n        return slow;\r\n    }\r\n\r\n    public static Node getReversedList(Node node) {\r\n        if (node == null || node.next == null) {\r\n            return node;\r\n        }\r\n\r\n        Node prev = null;\r\n        Node next = null;\r\n\r\n        while (node != null) {\r\n            next = node.next;\r\n            node.next = prev;\r\n            prev = node;\r\n            node = next;\r\n        }\r\n\r\n        return prev;\r\n    }\r\n\r\n    public static void main(String[] args) {\r\n        Node head = new Node(12);\r\n        head.next = new Node(4);\r\n        head.next.next = new Node(5);\r\n        head.next.next.next = new Node(9);\r\n        head.next.next.next.next = new Node(10);\r\n        head.next.next.next.next.next = new Node(6);\r\n\r\n        head = rearrangeListToHaveMinMaxElements(head);\r\n        while (head != null) {\r\n            System.out.print(head.data + &quot; &quot;);\r\n            head = head.next;\r\n        }\r\n    }\r\n}\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\r\n\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane \" id=\"tabs_desc_4890_2\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"Python\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"Python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\n# A Linked List Node\r\nclass Node:\r\n    def __init__(self, data=None, next=None):\r\n        self.data = data\r\n        self.next = next\r\n \r\n \r\n# Function to print a given linked list\r\ndef printList(head):\r\n \r\n    ptr = head\r\n    while ptr:\r\n        print(ptr.data, end=' ')\r\n        ptr = ptr.next\r\n \r\n \r\n \r\n# Rearrange the linked list so that it has alternating high, low values\r\ndef rearrange(head):\r\n \r\n    # empty list\r\n    if head is None:\r\n        return None\r\n \r\n    prev = head\r\n    curr = head.next\r\n \r\n    # start from the second node\r\n    while curr:\r\n \r\n        # if the previous node is greater than the current node, swap their values\r\n        if prev.data > curr.data:\r\n            temp = prev.data\r\n            prev.data = curr.data\r\n            curr.data = temp\r\n \r\n        # if the next node is greater than the current node, swap their values\r\n        if curr.next and curr.next.data > curr.data:\r\n            temp = curr.next.data\r\n            curr.next.data = curr.data\r\n            curr.data = temp\r\n \r\n        # update `prev` and `curr` node\r\n        prev = curr.next\r\n \r\n        if curr.next is None:\r\n            break\r\n \r\n        curr = curr.next.next\r\n \r\n    return head\r\n \r\n \r\nif __name__ == '__main__':\r\n \r\n    # input keys\r\n    keys = [12, 4, 5, 9, 10, 6]\r\n \r\n    head = None\r\n    for i in reversed(range(len(keys))):\r\n        head = Node(keys[i], head)\r\n \r\n    head = rearrange(head)\r\n    printList(head)\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\r\n\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t <\/div>\r\n\t\t\t\t\t \r\n\t\t\t\t <\/div>\r\n <script>\r\n\t\tjQuery(function () {\r\n\t\t\tjQuery('#myTab_4890 a:first').tab('show')\r\n\t\t});\r\n\t\t\r\n\t\t\t\tjQuery(function(){\r\n\t\t\tvar b=\"fadeIn\";\r\n\t\t\tvar c;\r\n\t\t\tvar a;\r\n\t\t\td(jQuery(\"#myTab_4890 a\"),jQuery(\"#tab-content_4890\"));function d(e,f,g){\r\n\t\t\t\te.click(function(i){\r\n\t\t\t\t\ti.preventDefault();\r\n\t\t\t\t\tjQuery(this).tab(\"show\");\r\n\t\t\t\t\tvar h=jQuery(this).data(\"easein\");\r\n\t\t\t\t\tif(c){c.removeClass(a);}\r\n\t\t\t\t\tif(h){f.find(\"div.active\").addClass(\"animated \"+h);a=h;}\r\n\t\t\t\t\telse{if(g){f.find(\"div.active\").addClass(\"animated \"+g);a=g;}else{f.find(\"div.active\").addClass(\"animated \"+b);a=b;}}c=f.find(\"div.active\");\r\n\t\t\t\t});\r\n\t\t\t}\r\n\t\t});\r\n\t\t\r\n\r\n\t\tfunction do_resize(){\r\n\r\n\t\t\tvar width=jQuery( '.tab-content .tab-pane iframe' ).width();\r\n\t\t\tvar height=jQuery( '.tab-content .tab-pane iframe' ).height();\r\n\r\n\t\t\tvar toggleSize = true;\r\n\t\t\tjQuery('iframe').animate({\r\n\t\t\t    width: toggleSize ? width : 640,\r\n\t\t\t    height: toggleSize ? height : 360\r\n\t\t\t  }, 250);\r\n\r\n\t\t\t  toggleSize = !toggleSize;\r\n\t\t}\r\n\r\n\r\n\t<\/script>\r\n\t\t\t\t\r\n\t\t\t\n<pre><code>Output\n4 12 5 10 6 9<\/code><\/pre>\n<p><strong>Time Complexity of Rearrange linked list in alternate last and first<\/strong>: O(n*logn), where n is the number of nodes. <\/p>\n<ul>\n<li>O(n*logn) time is used to sort the list. <\/li>\n<li>O(n) time is used to find the mid element. <\/li>\n<li>O(n) time is used to reverse the list.<\/li>\n<li>O(n) to create the resultant list from the first list and reversed list.<br \/>\nSumming up we get O(n<em>logn + n + n + n) = O(n<\/em>logn).<\/li>\n<\/ul>\n<p><strong>Conclusion<\/strong><\/p>\n<p>So, in this blog, we have tried to explain the Rearrange linked list in alternate last and first such that it consists of alternating minimum-maximum elements in the most efficient way. We hope you were able to take away critical techniques likes reversing a linked list slow and fast pointer approach, a two-pointer approach, etc. Also, If you want to solve more problems on Linked List, which our expert mentors at PrepBytes curate, you can follow this link <a href=\"https:\/\/mycode.prepbytes.com\/interview-coding\/practice\/linked-list\">Linked List<\/a>.<\/p>\n<h2>FAQs related to Rearrange linked list in alternate last and first<\/h2>\n<p><strong>1. How do I return a linked list size?<\/strong><br \/>\nThere are many ways we can return a linked list\u2019s size. The first way is to traverse the list and increment the size when each node is visited. This is an O(n) approach. But suppose we want to answer online queries, then manipulating the size while adding and deleting nodes will help answer each question to find the size of the list, which will be O(1).<\/p>\n<p><strong>2. How do you reverse a linked list in K groups?<\/strong><br \/>\nReversing a linked list in K groups can be done recursively and iteratively. For each group of k elements starting from the root node, the basic concept is to reverse the k group linked list and then move to the head of the next group of K elements if it exists in the linked list. Repeat the same process until it reaches termination.<\/p>\n<p><strong>3. How do you reorder a linked list?<\/strong><br \/>\nReordering a linked list can be done using many techniques such as slow-fast pointers, two-pointers, recursion, etc.<\/p>\n<p><strong>4. Why do we need a dummy node in the linked list?<\/strong><br \/>\nA dummy node is needed to carry out the operations of the linked list. Since we need to manipulate pointers within the linked list, we might lose the actual linked list if we manipulate without using a dummy pointer.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>This article taught you the most interesting and efficient problem of the linked list \u201cRearrange linked list in alternate last and first\u201d. We will see the approach, algorithms, dry run, and code implementation. We hope this article will enhance your knowledge of the linked list. Let us understand the problem statement of Rearrange linked list [&hellip;]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[143],"tags":[],"class_list":["post-4888","post","type-post","status-publish","format-standard","hentry","category-java"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v25.8 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Rearrange linked list consisting alternating minimum-maximum elements<\/title>\n<meta name=\"description\" content=\"Learn the most efficient way to rearrange a given list such that it consists of alternating minimum-maximum elements.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Rearrange linked list consisting alternating minimum-maximum elements\" \/>\n<meta property=\"og:description\" content=\"Learn the most efficient way to rearrange a given list such that it consists of alternating minimum-maximum elements.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/\" \/>\n<meta property=\"og:site_name\" content=\"PrepBytes Blog\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/prepbytes0211\/\" \/>\n<meta property=\"article:published_time\" content=\"2021-09-13T02:35:28+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2022-12-13T12:04:59+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000410738-Article_130.png\" \/>\n<meta name=\"author\" content=\"PrepBytes\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"PrepBytes\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"5 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/\"},\"author\":{\"name\":\"PrepBytes\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/39fcf072e04987f16796546f2ca83c2e\"},\"headline\":\"Rearrange the given linked list such that it consists of alternating minimum-maximum elements\",\"datePublished\":\"2021-09-13T02:35:28+00:00\",\"dateModified\":\"2022-12-13T12:04:59+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/\"},\"wordCount\":1034,\"commentCount\":0,\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000410738-Article_130.png\",\"articleSection\":[\"Java\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/\",\"url\":\"https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/\",\"name\":\"Rearrange linked list consisting alternating minimum-maximum elements\",\"isPartOf\":{\"@id\":\"http:\/\/43.205.93.38\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000410738-Article_130.png\",\"datePublished\":\"2021-09-13T02:35:28+00:00\",\"dateModified\":\"2022-12-13T12:04:59+00:00\",\"description\":\"Learn the most efficient way to rearrange a given list such that it consists of alternating minimum-maximum elements.\",\"breadcrumb\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/#primaryimage\",\"url\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000410738-Article_130.png\",\"contentUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000410738-Article_130.png\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"http:\/\/43.205.93.38\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Java\",\"item\":\"https:\/\/prepbytes.com\/blog\/category\/java\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"Rearrange the given linked list such that it consists of alternating minimum-maximum elements\"}]},{\"@type\":\"WebSite\",\"@id\":\"http:\/\/43.205.93.38\/#website\",\"url\":\"http:\/\/43.205.93.38\/\",\"name\":\"PrepBytes Blog\",\"description\":\"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING\",\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"http:\/\/43.205.93.38\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"http:\/\/43.205.93.38\/#organization\",\"name\":\"Prepbytes\",\"url\":\"http:\/\/43.205.93.38\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"contentUrl\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"width\":160,\"height\":160,\"caption\":\"Prepbytes\"},\"image\":{\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/www.facebook.com\/prepbytes0211\/\",\"https:\/\/www.instagram.com\/prepbytes\/\",\"https:\/\/www.linkedin.com\/company\/prepbytes\/\",\"https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA\"]},{\"@type\":\"Person\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/39fcf072e04987f16796546f2ca83c2e\",\"name\":\"PrepBytes\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/850669d326db1e1531f04db0c63145d941c2a26792aaeee226a9e6675b0ac698?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/850669d326db1e1531f04db0c63145d941c2a26792aaeee226a9e6675b0ac698?s=96&d=mm&r=g\",\"caption\":\"PrepBytes\"},\"url\":\"https:\/\/prepbytes.com\/blog\/author\/prepbytes\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Rearrange linked list consisting alternating minimum-maximum elements","description":"Learn the most efficient way to rearrange a given list such that it consists of alternating minimum-maximum elements.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/","og_locale":"en_US","og_type":"article","og_title":"Rearrange linked list consisting alternating minimum-maximum elements","og_description":"Learn the most efficient way to rearrange a given list such that it consists of alternating minimum-maximum elements.","og_url":"https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/","og_site_name":"PrepBytes Blog","article_publisher":"https:\/\/www.facebook.com\/prepbytes0211\/","article_published_time":"2021-09-13T02:35:28+00:00","article_modified_time":"2022-12-13T12:04:59+00:00","og_image":[{"url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000410738-Article_130.png","type":"","width":"","height":""}],"author":"PrepBytes","twitter_card":"summary_large_image","twitter_misc":{"Written by":"PrepBytes","Est. reading time":"5 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/#article","isPartOf":{"@id":"https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/"},"author":{"name":"PrepBytes","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/39fcf072e04987f16796546f2ca83c2e"},"headline":"Rearrange the given linked list such that it consists of alternating minimum-maximum elements","datePublished":"2021-09-13T02:35:28+00:00","dateModified":"2022-12-13T12:04:59+00:00","mainEntityOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/"},"wordCount":1034,"commentCount":0,"publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000410738-Article_130.png","articleSection":["Java"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/","url":"https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/","name":"Rearrange linked list consisting alternating minimum-maximum elements","isPartOf":{"@id":"http:\/\/43.205.93.38\/#website"},"primaryImageOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/#primaryimage"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000410738-Article_130.png","datePublished":"2021-09-13T02:35:28+00:00","dateModified":"2022-12-13T12:04:59+00:00","description":"Learn the most efficient way to rearrange a given list such that it consists of alternating minimum-maximum elements.","breadcrumb":{"@id":"https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/#primaryimage","url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000410738-Article_130.png","contentUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645000410738-Article_130.png"},{"@type":"BreadcrumbList","@id":"https:\/\/prepbytes.com\/blog\/rearrange-the-given-linked-list-such-that-it-consists-of-alternating-minimum-maximum-elements\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"http:\/\/43.205.93.38\/"},{"@type":"ListItem","position":2,"name":"Java","item":"https:\/\/prepbytes.com\/blog\/category\/java\/"},{"@type":"ListItem","position":3,"name":"Rearrange the given linked list such that it consists of alternating minimum-maximum elements"}]},{"@type":"WebSite","@id":"http:\/\/43.205.93.38\/#website","url":"http:\/\/43.205.93.38\/","name":"PrepBytes Blog","description":"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING","publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"http:\/\/43.205.93.38\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"http:\/\/43.205.93.38\/#organization","name":"Prepbytes","url":"http:\/\/43.205.93.38\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/","url":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","contentUrl":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","width":160,"height":160,"caption":"Prepbytes"},"image":{"@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/prepbytes0211\/","https:\/\/www.instagram.com\/prepbytes\/","https:\/\/www.linkedin.com\/company\/prepbytes\/","https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA"]},{"@type":"Person","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/39fcf072e04987f16796546f2ca83c2e","name":"PrepBytes","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/850669d326db1e1531f04db0c63145d941c2a26792aaeee226a9e6675b0ac698?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/850669d326db1e1531f04db0c63145d941c2a26792aaeee226a9e6675b0ac698?s=96&d=mm&r=g","caption":"PrepBytes"},"url":"https:\/\/prepbytes.com\/blog\/author\/prepbytes\/"}]}},"_links":{"self":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/4888","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/comments?post=4888"}],"version-history":[{"count":7,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/4888\/revisions"}],"predecessor-version":[{"id":10800,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/4888\/revisions\/10800"}],"wp:attachment":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/media?parent=4888"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/categories?post=4888"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/tags?post=4888"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}