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.

Difficulty: interview

Starter code:

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
    self.val = val
    self.next = next
class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        

Solutions:
# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def reorderList(self, head):
         """
         :type head: ListNode
         :rtype: void Do not return anything, modify head in-place instead.
         """
         if not head:
             return 
         fast, slow = head.next, head
         while fast and fast.next:
             fast = fast.next.next
             slow = slow.next
             
         
         p = slow.next
         slow.next = None
         node = None
         while p:
             nxt = p.next
             p.next = node
             node = p
             p = nxt
         
         p = head
         while node:
             tmp = node.next
             node.next = p.next
             p.next = node
             p = p.next.next
             node = tmp
             
             

# Definition for singly-linked list.
 # class ListNode:
 #     def __init__(self, x):
 #         self.val = x
 #         self.next = None
 
 class Solution:
     def reorderList(self, head):
         """
         :type head: ListNode
         :rtype: void Do not return anything, modify head in-place instead.
         """
         if not head:
             return None
         fast = slow = head
         temp = ListNode(0)
         while fast and fast.next:
             slow = slow.next
             fast = fast.next.next
         node = slow.next
         slow.next = None
         pre = None
         while node:
             cur = node.next
             node.next = pre
             pre = node
             node = cur
         first = head
         second = pre
         while first and second:
             node = first.next
             first.next = second
             second = second.next
             first.next.next = node
             first = node