Java | 2 Approach | 2 Pointer Approach
Solution 1 - Split linked list\n\n---\nsuppose we have two linkedList :\n>l1 =  1 -> 2 -> 3\n>l2 =  4 -> 5 -> 6 ,\n> l2rev = 6 -> 5  -> 4\n\n Now if  we have to
***Solution 1* - Split linked list**\n\n---\nsuppose we have two linkedList :\n>`l1 =  1 -> 2 -> 3`\n>` l2 =  4 -> 5 -> 6` ,\n> **l2rev** = ` 6 -> 5  -> 4 `\n\n* Now if  we have to merge **l1** and **l2rev** then this question is going to bit more simpler right\n\t**Now how do we merge :**\n\t\t**p1 =  l1**\n\t\t**p2 =  l2rev**\n\t* p1 is always point to node whose next is going to fill \n\t* p2 point to to node which is going to fill in **p1 next**\n\n**So steps involve are :**\n* split linkedlist into two halves\n\t* find mid and split\n\t* and revese second half\n* merge these two halves\n\n### Lets Code this Approch \uD83D\uDC69\uD83C\uDFFB\u200D\uD83D\uDCBB \uD83D\uDCBB\n---\n```\nclass Solution {\n    public ListNode midNode(ListNode head){\n        ListNode fast =  head, slow  =  head;\n        while(fast.next!=null && fast.next.next!=null){\n            fast =  fast.next.next;\n            slow =  slow.next;\n        }\n        return slow;\n    }\n    \n    public ListNode reverse(ListNode head){\n        ListNode curr =  head, prev=  null, next = null;\n        while(curr!=null){\n            next  =  curr.next;\n            curr.next =  prev ;\n            prev =  curr;\n            curr  =  next;\n        }\n        return prev;\n    }\n\n    \n    public void reorderList(ListNode head) {\n        \n        ListNode midNode =  midNode(head);\n        ListNode nextToMid =  midNode.next;\n        midNode.next = null;\n        ListNode p2 =  reverse(nextToMid);\n        \n        ListNode p1 =  head ,p1Next;    \n        while(p1!=null && p2!=null){\n            p1Next =  p1.next;                                    \n\t\t\tp1.next =  p2;\n\t\t\t           \n            p1 =  p2;\n            p2=p1Next;                        \n        }                \n    }            \n}\n```\n\n\n---\n\nTIME COMPLEXITY : **O(n)**\nSPACE COMPLEXITY : **O(1)**\n\n\n---\n\n\n***Solution 2* - Single traversal (Important concept)**\n\n---\n\n> Now let suppose we have two pointer left and right if we can move left **forward** and right **backward** then our task is going to simpler right \n\n**To merge we need to write only this much code**\n```\nLeftnext =  left.next;\nleft.next =  right;\nrigt.next =  Leftnext\nleft =  Leftnext\n```\n\n## let get more insight \uD83D\uDCA1\n---\n> ![image](https://assets.leetcode.com/users/images/cdd6b60d-d673-4de4-ac89-092616f07cdd_1640152889.938761.png)\n\n***Now How do we move two pointer one forward and one backward in linked list***\n- When we make recursion call on linkedlist then in post area of recursion call  our stack pointer is moving in backward direction:\n- And to move pointer in forward dirn at the same time , make it in heap , we have two ways to make it in heap\n\t 1. use class variable (declare outside the function)\n\t 2. Make one size array (it also created in heap), we are using this \n\n### Lets Code to get approch more better \uD83D\uDC69\uD83C\uDFFB\u200D\uD83D\uDCBB\uD83D\uDCBB :\n---\n```\n\nclass Solution {\n    public void reorderList(ListNode head) {\n        ListNode [] left =  new ListNode[1];// it will create in heap\n        left[0]  =  head;\n        reorder(left,head);\n        \n    }\n    \n    // left pointer will be created in heap and right pointer will be created in stack\n     public void reorder(ListNode left[],ListNode right){\n        if(right==null){\n            return ;\n        }\n        reorder(left,right.next);\n        \n    // in post area of recursion right pointer coming back(because of function remove from recursion stack)\n   // and we move left pointer forward \n        if(left[0].next!=null){\n            ListNode leftNext =  left[0].next;\n            left[0].next =  right;\n            right.next =  leftNext;\n            left[0] =  leftNext;            \n        }\n        \n    // as we need to  merge till left pointer behind the right pointer \n        if(left[0].next == right){\n            left[0].next =  null;\n        }                        \n    }\n}\n```\n\n---\nTIME COMPLEXITY : **O(n)**\nSPACE COMPLEXITY : **O(n), if we consider recursion stack**\n\n\n---\n\n
['Two Pointers', 'Java']