HM221 链表翻转排序

来源： 第 221 集 list容器-反转和排序

难度： 普及-

时间限制： 1s

空间限制： 64MB

题目描述

链表可以整表首尾对调，也可以排序。反转用成员函数 reverse（不要和动态数组预留空间的 reserve 搞混）。例如 \(1\,2\,3\,4\,5\) 反转后变成 \(5\,4\,3\,2\,1\)。

排序必须调用**成员函数** sort。链表迭代器不支持随机访问，因此**不能**把 [begin, end) 交给 <algorithm> 里的全局 sort，那样无法通过编译或运行。

成员 sort 默认按从小到大升序。若要降序，再提供一个返回 bool 的比较函数：两个整数 \(v_1,v_2\)，当希望 \(v_1\) 排在 \(v_2\) 前面时返回真。降序就让「前一个大于后一个」为真。

打印使用 const 引用和 const_iterator。

对输入序列依次做：原序列、reverse、默认 sort、带比较函数的降序 sort。每一步都输出整表。

输入格式

第一行一个整数 \(n\)。

第二行 \(n\) 个整数。当 \(n=0\) 时本行可以是空行。

输出格式

共四行，依次为：原序列、反转后、升序后、降序后。每行空格分隔，行末无多余空格。空链表输出空行。

样例

输入 #1

5
20 10 50 40 30

输出 #1

20 10 50 40 30
30 40 50 10 20
10 20 30 40 50
50 40 30 20 10

输入 #2

1
8

输出 #2

8
8
8
8

说明

\(0 \le n \le 1000\)，元素绝对值不超过 \(10^9\)。

样例 #1：先首尾对调得到 \(30\,40\,50\,10\,20\)；成员 sort 默认升成 \(10\,20\,30\,40\,50\)；再按「前一个大于后一个」降成 \(50\,40\,30\,20\,10\)。必须使用 list 的成员 sort，不要用全局 sort。