




def        lowerCAmelCase_			(  snake_case_  ):
      if not head:
            return True
      # split the list to two parts
      _A    ,     _A							:  Union[str, Any]    =		head.next, head
      while fast and fast.next:
            _A							:  Union[str, Any]    =		fast.next.next
            _A							:  List[Any]    =		slow.next
      _A							:  Optional[Any]    =		slow.next
      _A							:  Union[str, Any]    =		None  # Don't forget here! But forget still works!
      # reverse the second part
      _A							:  List[str]    =		None
      while second:
            _A							:  str    =		second.next
            _A							:  str    =		node
            _A							:  Tuple    =		second
            _A							:  List[str]    =		nxt
      # compare two parts
      # second part has the same or one less node
      while node:
            if node.val != head.val:
                  return False
            _A							:  List[str]    =		node.next
            _A							:  int    =		head.next
      return True







def        lowerCAmelCase_			(  snake_case_  ):
      if not head or not head.next:
            return True

      # 1. Get the midpoint (slow)
      _A							:  Tuple    =		head
      while fast and fast.next:
            _A    ,     _A							:  Dict    =		fast.next.next, slow.next

      # 2. Push the second half into the stack
      _A							:  Any    =		[slow.val]
      while slow.next:
            _A							:  Dict    =		slow.next
            stack.append(slow.val  )

      # 3. Comparison
      while stack:
            if stack.pop() != cur.val:
                  return False
            _A							:  Optional[Any]    =		cur.next

      return True







def        lowerCAmelCase_			(  snake_case_  ):
      if not head or not head.next:
            return True
      _A							:  int    =		{}
      _A							:  Optional[int]    =		0
      while head:
            if head.val in d:
                  d[head.val].append(snake_case_  )
            else:
                  _A							:  List[Any]    =		[pos]
            _A							:  int    =		head.next
            pos += 1
      _A							:  Tuple    =		pos - 1
      _A							:  str    =		0
      for v in d.values():
            if len(snake_case_  ) % 2 != 0:
                  middle += 1
            else:
                  _A							:  Dict    =		0
                  for i in range(0,len(snake_case_  )  ):
                        if v[i] + v[len(snake_case_  ) - 1 - step] != checksum:
                              return False
                        step += 1
            if middle > 1:
                  return False
      return True







import operator







def        lowerCAmelCase_			(  snake_case_,snake_case_ = False,snake_case_ = None  ):
      _A							:  str    =		operator.lt if reverse else operator.gt
      _A							:  Optional[Any]    =		solution or []

      if not arr:
            return solution

      _A							:  Dict    =		[arr.pop(0  )]
      for i, item in enumerate(snake_case_  ):
            if _operator(snake_case_,sublist[-1]  ):
                  sublist.append(snake_case_  )
                  arr.pop(snake_case_  )

    #  merging sublist into solution list
      if not solution:
            solution.extend(snake_case_  )
      else:
            while sublist:
                  _A							:  Union[str, Any]    =		sublist.pop(0  )
                  for i, xx in enumerate(snake_case_  ):
                        if not _operator(snake_case_,snake_case_  ):
                              solution.insert(snake_case_,snake_case_  )
                              break
                  else:
                        solution.append(snake_case_  )

      strand_sort(snake_case_,snake_case_,snake_case_  )
      return solution


if __name__ == "__main__":
  assert strand_sort([4, 3, 5, 1, 2]) == [1, 2, 3, 4, 5]
  assert strand_sort([4, 3, 5, 1, 2], reverse=True) == [5, 4, 3, 2, 1]

