如何实现奇偶链表、旋转链表和分隔链表的操作？

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

328. 奇偶链表题目

328. 奇偶链表项目给定向量表的一个单链表，要求将链表中的奇数节点和偶数节点分别排列在一起。请注意，这里的奇数节点和偶数节点指的是节点的值，而不是节点本身。请将所有的奇数节点和偶数节点分别排列在一起。

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 的后一个节点是偶数链表的头节点。令 evenHead head.next则 evenHead 是偶数链表的头节点。