Basically we need 3 steps to solve this problem. First, use two pointers to break original linked list into two
equal length parts (exactly equals when we have even listnode, differs 1 when odd cases). Then, reverse the latter part. Finally, reconstruct the whole linked list.
Since the length of latter part is always equal or smaller than the other one, we only need to examine whether the pointer of latter part meets the end in the last step.
class Solution(object): def reorderList(self, head): """ :type head: ListNode :rtype: void Do not return anything, modify head in-place instead. """ if not head: return head # break linked list into two "equal" length parts slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next p = slow.next slow.next = pre = None # reverse the latter part while p: p.next, pre, p = pre, p, p.next # reconstruct the whole linked list p = head while pre: p.next, pre.next, p, pre = pre, p.next, p.next, pre.next