重排链表

题目描述：给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln-1 → Ln 请将其重新排列后变为：

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例说明请见LeetCode官网。

来源：力扣（LeetCode）   

链接：https://leetcode-cn.com/problems/reorder-list/   

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解法一：链表遍历

首先，如果链表为空或链表只有一个节点，直接返回。

否则，首先用一个栈nodes记录所有的节点，并记录链表节点的数量count；

然后，记录插入的顺序，遍历到奇数位时，从头结点方向插入链表；遍历到偶数位时，从栈中取出节点（即从尾结点方向）插入链表。

【每日寄语】 人不怕有理想，不怕有梦想。也不管它又多大，又有多远！只要你客观的认清自己，在道德规范之内，坚持自己，做你想做的，一定会有收获的那一天！