链表328、61、86、725，能否一招分隔奇偶旋转链表？

本文共计2534个文字，预计阅读时间需要11分钟。

题目：328. 奇偶链表题目描述：给定一个单链表，将链表中的所有奇数节点和偶数节点分别排列在一起。请注意，这里的奇数节点和偶数节点指的是节点的值，而不是节点的位置。请将所有奇数节点和偶数节点分别排列在一起。

例如，如果输入链表的节点值为 [1, 2, 3, 4, 5]，则输出应为 [1, 3, 5, 2, 4]。

328.奇偶链表题目328.奇偶链表给定一个单链表把所有的奇数节点和偶数节点分别排在一起。请注意这里的奇数节点和偶数节点指的是节点编号的奇偶性把所有的奇数节点和偶数节点分别排在一起。请注意这里的奇数节点和偶数节点指的是节点编号的奇偶性而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)时间复杂度应为 O(nodes)nodes 为节点总数。

示例 1:

输入: 1->2->3->4->5->NULL 输出: 1->3->5->2->4->NULL 示例 2:

输入: 2->1->3->5->6->4->7->NULL 输出: 2->3->6->7->1->5->4->NULL 说明:

应当保持奇数节点和偶数节点的相对顺序。 链表的第一个节点视为奇数节点第二个节点视为偶数节点以此类推。

解法

如果链表为空则直接返回链表。

对于原始链表每个节点都是奇数节点或偶数节点。头节点是奇数节点头节点的后一个节点是偶数节点相邻节点的奇偶性不同。因此可以将奇数节点和偶数节点分离成奇数链表和偶数链表然后将偶数链表连接在奇数链表之后合并后的链表即为结果链表。

原始链表的头节点 head 也是奇数链表的头节点以及结果链表的头节点head 的后一个节点是偶数链表的头节点。