Detailed and Easy Python Solution for noobs like me :)
Question\n\nYou are given the head of a singly linked list. The list can be represented as:\n\n\nL0 \u2192 L1 \u2192 \u2026 \u2192 Ln - 1 \u2192 Ln\n\n\nReorder
### Question\n\nYou are given the head of a singly linked list. The list can be represented as:\n\n```\nL0 \u2192 L1 \u2192 \u2026 \u2192 Ln - 1 \u2192 Ln\n```\n\n*Reorder the list to be on the following form:*\n\n```\nL0 \u2192 Ln \u2192 L1 \u2192 Ln - 1 \u2192 L2 \u2192 Ln - 2 \u2192 \u2026\n\n```\n\nYou may not modify the values in the list\'s nodes. Only nodes themselves may be changed.\n\n```\nInput: head = [1,2,3,4]\nOutput: [1,4,2,3]\n\nInput: head = [1,2,3,4,5]\nOutput: [1,5,2,4,3]\n```\n\n### Brainstorming.\n\n1. L0 \u2192 L1 \u2192 \u2026 \u2192 Ln - 1 \u2192 Ln covert to \u2014> L0 \u2192 Ln \u2192 L1 \u2192 Ln - 1 \u2192 L2 \u2192 Ln - 2 \u2192\n    1. FirstElement \u2014> lastElement \u2014> Second Element \u2014> Second LastElement\n    \n    ```python\n    \n    1->2->3->4. to 1->4->2->3\n  \n    \n    How will we approach this situation, we have a linked list and we have to merge\n    in a way that it comes to something like this.\n    FirstElement \u2014> lastElement(n-1) \u2014> Second Element \u2014> Second LastElement(n-2) ...\n    \n    If we look at the final output we can see they look something like two arrays \n    being merged based on the same indexes.\n    [1,2] [4,3]--this is the reverse of the second half of the list\n     ^.    ^\n    \n    we are merging the first element from array one and then taking the second element\n    from array 2 and merging them into a new array.\n    first Step\n    [1,2] [4,3]\n     ^.    ^\n    1->4\n    Second Step\n    [1,2] [4,3]\n       ^.    ^\n    1->4->2->3\n    \n    This is the intuition we will be using to solve the problem.\n    \n    Making two arrays out of the linkedList and then joining one with the other in \n    reverse order.\n    \n    Since we are in a linked list we have no idea what is the lenght of an array.\n    ```\n    \n2. How can we find the lenght of the array and also its half if we need to make that merger.\n    \n    ```python\n    How can we use pointers\n    1->2->3->4\n    ^  ^\n    s. f\n    \n    imagine we have a slow pointer and a fast pointer. The fast pointer goes twice as\n    fast as the slow pointer. When the fast pointer reaches the end of the array, where \n    will the fast pointer be? half Way!\n    \n    First\n    1->2->3->4\n    ^  ^\n    s. f\n    \n    Second\n    1->2->3->4\n       ^     ^\n       s     f\n    \n    How ever there is one catch here, lets say that the lenght of the array is odd\n    What will happen then?\n    \n    First\n    1->2->3->4->5\n    ^  ^\n    s. f\n    \n    Second\n    1->2->3->4->5\n       ^     ^\n       s     f\n    \n    Third\n    1->2->3->4->5->None\n          ^         ^\n          s         f\n    \n    In the odd case the first array will be larger than the second array by one index\n    l1 = [1,2,3]\n    l2 = [4,5]\n    \n    How can we write this in code?\n    \n    input : head\n    \n    s(slowPointer) = head\n    s(fastPointer) = head.next\n    \n    while f and f.next: \n    \n    \ts = s.next\n    \tf = f.next.next\n    \n    #secondHalfStart = second\n    second = s.next\n    \n    ```\n    \n3. Now we know where the second half of the list begins how can we use that information?\n    1. [reverse a linked list](https://www.notion.so/reverse-a-linked-list-6ff7e58a12d346e9a9645057dae75e26) reference and detail for reversing a linked list and why we will use a temp varaible\n    \n    ```python\n    1->2->3->4\n          ^\n          second\n    \n    What if we start from the half and reverse the list after it.\n    \n    1->2<-3<-4-None\n             ^\n             second Pointer is now at the end\n    \n    1->2<-3<-4\n    \n    Code\n    #reverse the second Half \n    #setting s to none as well, so when the we are merging the two list we know\n    # where the array ends and become two seprate array.\n    1->2->None <-3<-4<-None\n    \n    prev,s.next = None \n    while second:\n    \ttemp = second.next\n    \tsecond.next = prev\n    \tprev = second\n    \tsecond = temp\n    \n    #the second half has been reversed.\n    \n    ```\n    \n4. How will we merge these two lists we have\n    \n    ```python\n    Now have the array we can start with two sides and keep merging them\n    \n    First Iteration\n    1->2->None None<-3<-4 to 1->4\n    ^.                  ^ \t\t\t\t\t\t\t\t\t\t\n    First              Second  \n    \n    Second iteration\n    \n    First Iteration\n    1->2->None None<-3<-4 to 1->4->2->3\n       ^.            ^ \t\t\t\t\t\t\t\t\t\t\n       First         Second  \n    \n    We are done! now we can write the code.\n    \n    first, second = head, prev\n    \n    while second:\n    \t\ttemp1, temp2 = first.next, second.next\n    \n    \t\tfirst.next = second\n    \t\tsecond.next = temp1\n    \t\tfirst = temp1 \n    \t\tsecond = temp2 \n    \n    ```\n    \n5. Lets code now\n    \n    ```python\n    # Definition for singly-linked list.\n    # class ListNode:\n    #     def __init__(self, val=0, next=None):\n    #         self.val = val\n    #         self.next = next\n    class Solution:\n        def reorderList(self, head: Optional[ListNode]) -> None:\n            """\n            Do not return anything, modify head in-place instead.\n            """\n            \n            # find the half\n            slow, fast = head, head.next\n            \n            while fast and fast.next:\n                slow = slow.next\n                fast = fast.next.next\n                \n            half = slow.next\n            slow.next = None\n            prev = None\n            \n            # Reverse the second half\n            \n            while half:\n                temp = half.next\n                half.next = prev \n                prev = half\n                half = temp\n                \n            \n            # merge the two lists\n            \n            first, second = head, prev\n            \n            while second:\n                temp1, temp2 = first.next, second.next\n                \n                first.next = second\n                second.next = temp1\n                first = temp1\n                second = temp2\n    ```
['Python']