#143

from utils.listNode import ListNode

class Solution:
    def reorder(self, head):
        if not head:
            return head
        
        fast, slow = head, head

        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
        
        rev, node = None, slow
        while node:
            rev, rev.next, node = node, rev, node.next
        
        first, second = head, rev
        while second.next:
            first.next, first = second, first.next
            second.next, second = first, second.next
        
        return head


class Solution2:
    def reorder(self, head):
        list_map = dict()
        curr, i = head, 1
        while curr:
            list_map[i] = curr
            curr = curr.next
            i += 1
        
        left, right = 1, i - 1

        node = head
        while left <= right:
            node.next = list_map[right]
            left += 1

            if left <= right:
                node = node.next
                node.next = list_map[left]
                right -= 1
                node = node.next
        
        node.next = None

        return head

one = ListNode(1)
two = ListNode(2)
three = ListNode(3)
four = ListNode(4)
five = ListNode(5)

one.next = two
two.next = three
three.next = four
four.next = five

print(one)

solution = Solution()
print(solution.reorder(one))

def reorder(head):
    if not head:
        return None
    
    slow = fast = head

    while fast and fast.next:
        fast = fast.next.next
        slow = slow.next
    
    rev = ListNode(None)
    while slow:
        rev, rev.next, slow = slow, rev, slow.next
    
    first, second = head, rev
    while second.next:
        first.next, first = second, first.next
        second.next, second = first, second.next
