文章目录

1. 1. Odd Even Linked List

Odd Even Linked List

---

给定一个单向链表，将第奇数个节点的值组合起来，第偶数个节点的值组合起来。最终串在一起。比如1->2->3->4->5->NULL，结果是1->3->5->2->4->NULL

直接的方法就是记录奇数数列和偶数数列，最后将奇数数列的尾巴指向偶数数列的尾巴。这样做的时间复杂度是O(N),空间复杂度也是O(N)。无论怎么做，总归是要扫一遍数组的，那么可以优化的就是空间复杂度。我们可以直接在链表上操作，用3个节点，第一个节点是偶数数列的头，第二个是遍历奇数数列，第三个是遍历偶数数列。最后将第二个节点指向第一个节点即可。