(1)
通过两个指针*i和*j，i从1到n/2，j从n到 n/2 + 1，将j所指向的节点依次插入到i之后。

(2)
node *Sort(node *head)
{
  if (head == nullptr || head->next == nullptr) {
    return;
  }
  node *i = head->next;
  // i 之后如果还存在节点 
  while (i->next != nullptr) {
    // 尝试查找一个可以插入在i之后的p节点
    node *j = i->next;
    if (j->next == nullptr) {
      break;
    }
    // 找到需要插在i->next的节点的prev节点
    while(j->next->next != nullptr) {
      j = j->next;
    }
    // 将p插入到i和i->next之间
    node *p = j->next;
    p->next = i->next;
    i->next = p;
    j->next = nullptr;
    i = p->next;
  }
  return head;
}

(3)
时间复杂度O(n^2)。