[Python] 3 steps to success, explained
If you never solved singly linked lists problems before, or you do not have a lot of experience, this problem can be quite difficult. However if you already kno
If you never solved singly linked lists problems before, or you do not have a lot of experience, this problem can be quite difficult. However if you already know all the tricks, it is not difficult at all. Let us first try to understand what we need to do. For list `[1,2,3,4,5,6,7]` we need to return `[1,7,2,6,3,5,4]`. We can note, that it is actually two lists `[1,2,3,4]` and `[7,6,5]`, where elements are interchange. So, to succeed we need to do the following steps:\n1. Find the middle of or list - be careful, it needs to work properly both for even and for odd number of nodes. For this we can either just count number of elements and then divide it by to, and do two traversals of list. Or we can use `slow/fast` iterators trick, where `slow` moves with speed `1` and `fast` moves with speed `2`. Then when `fast` reches the end, `slow` will be in the middle, as we need.\n2. Reverse the second part of linked list. Again, if you never done it before, it can be quite painful, please read oficial solution to problem **206. Reverse Linked List**. The idea is to keep **three** pointers: `prev, curr, nextt` stand for previous, current and next and change connections in place. Do not forget to use `slow.next = None`, in opposite case you will have list with loop.\n3. Finally, we need to merge two lists, given its heads. These heads are denoted by `head` and `prev`, so for simplisity I created `head1` and `head2` variables. What we need to do now is to interchange nodes: we put `head2` as next element of `head1` and then say that `head1` is now `head2` and `head2` is previous `head1.next`. In this way we do one step for one of the lists and rename lists, so next time we will take element from `head2`, then rename again and so on.\n\n**Complexity**: Time complexity is `O(n)`, because we first do `O(n)` iterations to find middle, then we do `O(n)` iterations to reverse second half and finally we do `O(n)` iterations to merge lists. Space complexity is `O(1)`.\n\n```\nclass Solution:\n    def reorderList(self, head):\n        #step 1: find middle\n        if not head: return []\n        slow, fast = head, head\n        while fast.next and fast.next.next:\n            slow = slow.next\n            fast = fast.next.next\n        \n        #step 2: reverse second half\n        prev, curr = None, slow.next\n        while curr:\n            nextt = curr.next\n            curr.next = prev\n            prev = curr\n            curr = nextt    \n        slow.next = None\n        \n        #step 3: merge lists\n        head1, head2 = head, prev\n        while head2:\n            nextt = head1.next\n            head1.next = head2\n            head1 = head2\n            head2 = nextt\n```\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
['Two Pointers']