Reorder List

[huimeich]

Given a singly linked list L: L0→L1→…→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list's nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3. Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

[huimeich]

def reorderList(self, head: ListNode) -> None:
    """
    Do not return anything, modify head in-place instead.
    """
    if head == None: return
    left = head
    right = head
    while right and right.next:
        left = left.next
        right = right.next.next
    mid = left
    right = mid.next if mid else None
    mid.next = None
    while mid and right:
        right_next = right.next
        right.next = mid
        mid = right
        right = right_next
    mid = right if right else mid
    left = head
    while left and mid and left.next != mid:
        left_next = left.next if left else None
        mid_next = mid.next if mid else None
        left.next = mid
        mid.next = left_next
        left = left_next
        mid = mid_next

[huimeich]

def reorderList(self, head: ListNode) -> None:
    if not head:
        return

    nodes = []
    curr = head

    while curr:
        nodes.append(curr)
        curr = curr.next

    n = len(nodes)
    middle = n // 2

    for i in range(middle):
        nodes[i].next = nodes[n-1-i]
        nodes[n-1-i].next = nodes[i+1]

    nodes[middle].next = None