static Node sort ( Node head ) {
  if ( head == null || head . next == null ) {
    return head ;
  }
  Node front = head ;
  Node last = head ;
  Node res = new Node ( ) ;
  Node resEnd = res ;
  Node next ;
  while ( last . next != null ) {
    last = last . next ;
  }
  while ( front != last ) {
    if ( last . data <= front . data ) {
      resEnd . next = last ;
      next = last . prev ;
      last . prev . next = null ;
      last . prev = resEnd ;
      last = next ;
      resEnd = resEnd . next ;
    }
    else {
      resEnd . next = front ;
      next = front . next ;
      front . next = null ;
      front . prev = resEnd ;
      front = next ;
      resEnd = resEnd . next ;
    }
  }
  resEnd . next = front ;
  front . prev = resEnd ;
  return res . next ;
}

static Node sort ( Node head ) { if ( head == null || head . next == null ) { return head ; } Node front = head ; Node last = head ; Node res = new Node ( ) ; Node resEnd = res ; Node next ; while ( last . next != null ) { last = last . next ; } while ( front != last ) { if ( last . data <= front . data ) { resEnd . next = last ; next = last . prev ; last . prev . next = null ; last . prev = resEnd ; last = next ; resEnd = resEnd . next ; } else { resEnd . next = front ; next = front . next ; front . next = null ; front . prev = resEnd ; front = next ; resEnd = resEnd . next ; } } resEnd . next = front ; front . prev = resEnd ; return res . next ; }
(method_declaration (modifiers) type: (type_identifier) name: (identifier) parameters: (formal_parameters (formal_parameter type: (type_identifier) name: (identifier))) body: (block (if_statement condition: (parenthesized_expression (binary_expression left: (binary_expression left: (identifier) right: (null_literal)) right: (binary_expression left: (field_access object: (identifier) field: (identifier)) right: (null_literal)))) consequence: (block (return_statement (identifier)))) (local_variable_declaration type: (type_identifier) declarator: (variable_declarator name: (identifier) value: (identifier))) (local_variable_declaration type: (type_identifier) declarator: (variable_declarator name: (identifier) value: (identifier))) (local_variable_declaration type: (type_identifier) declarator: (variable_declarator name: (identifier) value: (object_creation_expression type: (type_identifier) arguments: (argument_list)))) (local_variable_declaration type: (type_identifier) declarator: (variable_declarator name: (identifier) value: (identifier))) (local_variable_declaration type: (type_identifier) declarator: (variable_declarator name: (identifier))) (while_statement condition: (parenthesized_expression (binary_expression left: (field_access object: (identifier) field: (identifier)) right: (null_literal))) body: (block (expression_statement (assignment_expression left: (identifier) right: (field_access object: (identifier) field: (identifier)))))) (while_statement condition: (parenthesized_expression (binary_expression left: (identifier) right: (identifier))) body: (block (if_statement condition: (parenthesized_expression (binary_expression left: (field_access object: (identifier) field: (identifier)) right: (field_access object: (identifier) field: (identifier)))) consequence: (block (expression_statement (assignment_expression left: (field_access object: (identifier) field: (identifier)) right: (identifier))) (expression_statement (assignment_expression left: (identifier) right: (field_access object: (identifier) field: (identifier)))) (expression_statement (assignment_expression left: (field_access object: (field_access object: (identifier) field: (identifier)) field: (identifier)) right: (null_literal))) (expression_statement (assignment_expression left: (field_access object: (identifier) field: (identifier)) right: (identifier))) (expression_statement (assignment_expression left: (identifier) right: (identifier))) (expression_statement (assignment_expression left: (identifier) right: (field_access object: (identifier) field: (identifier))))) alternative: (block (expression_statement (assignment_expression left: (field_access object: (identifier) field: (identifier)) right: (identifier))) (expression_statement (assignment_expression left: (identifier) right: (field_access object: (identifier) field: (identifier)))) (expression_statement (assignment_expression left: (field_access object: (identifier) field: (identifier)) right: (null_literal))) (expression_statement (assignment_expression left: (field_access object: (identifier) field: (identifier)) right: (identifier))) (expression_statement (assignment_expression left: (identifier) right: (identifier))) (expression_statement (assignment_expression left: (identifier) right: (field_access object: (identifier) field: (identifier)))))))) (expression_statement (assignment_expression left: (field_access object: (identifier) field: (identifier)) right: (identifier))) (expression_statement (assignment_expression left: (field_access object: (identifier) field: (identifier)) right: (identifier))) (return_statement (field_access object: (identifier) field: (identifier)))))