给大家整理了一个算法速刷 TOP101 题单，按照标签进行分类刷题，涵盖了链表、二分查找、排序、二叉树、堆、栈、队列、哈希、递归、回溯算法、动态规划、字符串、双指针、贪心算法、模拟算法等多个高频知识考点，准备校招、临时突击算法面试的同学可以根据这份题单进行系统的刷题。
题单地址：https://www.algomooc.com/3080.html
一、题目描述
给定单链表的头结点 head ，将所有索引为奇数的结点和索引为偶数的结点分别组合在一起，然后返回重新排序的列表。
第一个结点的索引被认为是 奇数 ， 第二个结点的索引为 偶数 ，以此类推。
请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。
示例 1:
输入: head = [1,2,3,4,5]
输出: [1,3,5,2,4]
示例 2:
输入: head = [2,1,3,5,6,4,7]
输出: [2,3,6,7,1,5,4]
提示:
n ==链表中的结点数0 <= n <= 104-10^6 <= Node.val <= 10^6
二、题目解析
1、设置两个指针，分别为 odd 和 even。
2、odd 这个指针指向链表的头结点，后续的一系列操作过程中，会维护 odd 的指向，让 odd 始终指向所有已经完成重排结点当中的最后一个奇结点位置。
3、even 这个指针指向链表的头结点的下一个结点，后续的一系列操作过程中，会维护 even 的指向，让 even 始终指向所有已经完成重排结点当中的最后一个偶结点位置。
4、再设置一个指针 evenHead，固定不动，始终指向链表的头结点的下一个结点，它表示着偶结点开始的位置。
5、从偶数链表的头结点开始向后遍历，如果当前结点为空，或者后一结点为空，那么说明整个链表已经查看完毕，不需要再遍历了。
6、原先奇数结点的下一个结点是偶数结点，即 even 这个结点，根据数学知识，奇数后面一定是偶数，偶数后面一定是奇数，那么 even.next 结点必然是奇数结点，所以让 odd 这个奇数结点的 next 指针指向 even.next 这个奇数结点，这样，odd 上面都是奇数。
7、根据上面第 2 的要求，让 odd 移动到最新的由奇数结点组成的链表的尾部位置。
8、 这个时候，odd.next 必然是偶数结点，以让 even 这个偶数结点的 next 指针指向 odd.next 这个偶数结点。
9、根据上面第 3 的要求，让 even 移动到最新的由偶数结点组成的链表的尾部位置。
10、跳出循环后，原链表所有的结点已经遍历完毕，odd 上都是奇数结点，even 都是偶数结点，根据题目要求，奇数结点都在偶数结点之前，所以让此时右奇数结点组成的链表的尾部的 next 指针指向由偶数结点组成的链表的头部。
11、最后返回原链表的头部结点就可以了，链表的头部结点没有发生过变化，因为它是奇数结点，并且是第一个奇数结点。
三、参考代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 奇偶链表（ LeetCode 328 ）:https://leetcode-cn.com/problems/odd-even-linked-list/
class Solution {
public ListNode oddEvenList(ListNode head) {
// 边界情况处理，如果链表为空或者只有一个结点，返回 head 就行
if(head == null || head.next == null) return head;
// 设置一个指针，指向链表的头结点，odd 代表奇数结点的头结点
ListNode odd = head;
// 设置一个指针，指向链表的头结点的下一个结点，even 代表偶数结点的头结点
ListNode even = head.next;
// 设置一个指针，指向偶数结点的头结点，最终让奇数结点的尾结点的 next 指针指向它
ListNode evenHead = even;
// 从偶数链表的头结点开始向后遍历
// 如果当前结点为空，或者后一结点为空，那么说明整个链表已经查看完毕，不需要再遍历了
while(even != null && even.next != null){
// 原先奇数结点的下一个结点是偶数结点，即 even 这个结点
// 根据数学知识，奇数后面一定是偶数，偶数后面一定是奇数
// 那么 even.next 结点必然是奇数结点
// 所以让 odd 这个奇数结点的 next 指针指向 even.next 这个奇数结点
// 这样，odd 上面都是奇数
odd.next = even.next;
// 让 odd 移动到最新的由奇数结点组成的链表的尾部位置
odd = odd.next;
// 这个时候，odd.next 必然是偶数结点
// 所以让 even 这个偶数结点的 next 指针指向 odd.next 这个偶数结点
even.next = odd.next;
// 让 even 移动到最新的由偶数结点组成的链表的尾部位置
even = even.next;
}
// 此时，原链表所有的结点已经遍历完毕
// odd 上都是奇数结点
// even 都是偶数结点
// 根据题目要求，奇数结点都在偶数结点之前
// 所以让此时右奇数结点组成的链表的尾部的 next 指针指向由偶数结点组成的链表的头部
odd.next = evenHead;
// 最后返回原链表的头部结点就可以了
// 链表的头部结点没有发生过变化，因为它是奇数结点，并且是第一个奇数结点
return head;
}
}
