Reorder List - Easy Explaination Java
Problem Statement Explained\n\nThis question asks us to reorder a linked list in this way : L0 \u2192 Ln \u2192 L1 \u2192 Ln-1 \u2192 L2 \u2192 Ln-2 \u2192 \u20
# Problem Statement Explained\n\nThis question asks us to reorder a linked list in this way : L0 \u2192 Ln \u2192 L1 \u2192 Ln-1 \u2192 L2 \u2192 Ln-2 \u2192 \u2026 \n\nWe are going to use a stack for this problem because of the LIFO property of stack which will allow us to access the last element of the list.\n \n---\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nIn this question , we have to reorder a linked list . \nso , if a linked list is **1-2-3-4-5** , after re ordering , it will become  **1-5-2-4-3** .\nWhat we\'ll do now is , push all the nodes of the linked list into the stack.\nAnd to add do that , we first assign head\'s address to a local node temp. `ListNode temp = head` \n> This should be our first step in almost every linked list question because head doesn\'t move , hence we always assign it\'s address to a temporary pointer.\n\nAfter , pushing all nodes into the stack , we iterate for n/2 times and do the re-ordering of the list . \n\n**Why n/2 ?**\n\n> Each iteration processes two nodes: one from the start and one from the end of the list.\nIn a list of size \uD835\uDC5B, we need to do this pairing n/2 times to cover all nodes.\nFor a list of size 5:\nIteration 1: handles nodes 1 and 5.\nIteration 2: handles nodes 2 and 4.\n---\n# Code Walkthrough\n\nWhen we are iterating for n/2 times , we do the following assignments :\n```\nListNode next=temp.next;\nListNode last = stack.pop();\ntemp.next=last;\nlast.next=next;\ntemp=next;\n\n```\nLet\'s take an example of a Linked List `1-2-3-4-5`. After we push these elements inside the stack , our stack now contains : `5-4-3-2-1`\n(with `5` being on top of the stack , since it was the last processed in the list).\n\n1. In **`For i=0`** : we assign `next` node with the next of `temp`.\nas in line of code `ListNode next=temp.next;`  so now,  `temp = 1` . \nthen `last node` is initialized with stack.pop() which means that `last = 5`. \n\nSo now , we link these nodes together in the order we want .\n`\n                temp.next=last;\n                last.next=next;\n                    temp=next;`\nthis gives us 1-5-2-3-4 ,the stack contains [4,3,2,1] and the temp points to 2 now\n\n2. **`For i=1`** : next =3 , last = 4 and after linking the nodes , we get 1-5-2-4-3 and temp =3.\n\n3. **`For i=2`** : (n/2 iterations are completed ) temp = 3 and 3 points to null now , which means list has terminated.\n\n\n---\n# Complexity\n- Time complexity : $$O(n)$$\n<!-- Add your time complexity here, e.g.  -->\n\n- Space complexity : $$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n---\n\n# Code\n```\n/**\n * Definition for singly-linked list.\n * public class ListNode {\n *     int val;\n *     ListNode next;\n *     ListNode() {}\n *     ListNode(int val) { this.val = val; }\n *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }\n * }\n */\nclass Solution {\n    public void reorderList(ListNode head) {\n        Stack<ListNode>stack = new Stack<>();\n      if(head==null || head.next==null)\n      {\n        return;\n      }\n\n      ListNode temp=head;\n\n      while(temp!=null)\n      {\n        stack.push(temp);\n        temp=temp.next;\n      }\n               \n               int n  = stack.size();\n               temp=head;\n\n               for(int i=0;i<n/2;i++)\n               {\n                ListNode next=temp.next;\n                ListNode last = stack.pop();\n\n                temp.next=last;\n                last.next=next;\n                    temp=next;\n                \n\n               }\n\n               temp.next=null;\n    }\n}\n```\n---\n**Feel free to discuss this problem in the comments section and also , do upvote if you liked the explaination ThankYou !**
['Linked List', 'Two Pointers', 'Stack', 'Java']