给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。
请尝试使用原地算法完成。
你的算法的空间复杂度应为 O(1),
说明: 应当保持奇数节点和偶数节点的相对顺序。
链表的第一个节点视为奇数节点,第二个节点视为偶数节点,以此类推。
如果用辅助数组来做,非常简单,但是不满足题目的要求,因为题目要求空间复杂度 O(1),意味着不能额外申请辅助数组,换一个思路,考虑用一个整型变量来记录遍历的位置是奇数还是偶数,然后用四个指针分别记录当前奇数链表的开头,结尾;偶数链表的开头和结尾,最后把两个链表串联起来即可,所以,只需要设置五个变量即可完成整个算法。
整个流程如下,遍历 cur 指针,同步记录 count,如果 count 记录的位置是奇数, 则构造奇数链表,如果 count 位置记录的是偶数,则构造偶数链表。
构造的过程也比较简单,以构造奇数链表为例:
构造偶数链表的过程和构造奇数链表的过程同理,不赘述。
构造好两个链表以后,把两个链表连接起来即可,连接的逻辑如下: