Question

请教一道数据结构的算法题算法具体描述如下： 设以带头结点的双向循环链表L=（a1,a2,....,an).试写一个时

Answer 1

有两种思想供参考：（1）
整体思想

（2）化整为零
先来说说整体思想，我们可以发现序号为奇数的元素的前后相对位置未变，只是偶数位置有变化。这样的话，我们可以将偶数按序号
逆序
（由大到小）插入到
链表
尾部。考虑到
时间复杂度
问题，在搜索偶数的过程中，可以先找到最大的偶数序号+1的位置（是个奇数，奇数相对位置不动），记下它的位置为L，L向前指的那个位置是偶数位置。这样再找下一个时，直接用L-2，直至k-2等于3为止即可找到所有序号为偶数的位置。
怎么化整为零呢？先来看看下面这个过程：
null
1
2
（1是从head的后面插入链表，2是从tail的前面插入链表）
1
3
2
（3是从1的后面插入链表）
1
3
4
2（4是从2的前面插入链表）
1
3
5
4
2（5是从3的后面插入链表）
......
1
3
5
...
n
...
6
4
2
由此，我们可以设置2个指针p，q，分别指向刚刚序号为奇数的元素插入的位置和刚刚序号为奇数的元素插入的位置，下一个序号为奇数的元素插入到p后，为偶数的插入到q前，并随着插入的过程实时变化p，q，最后再将q和q指向的元素之间的2个指针接上就OK了。
程序交给你来写吧，应该不太难。

Answer 2

你好！
很简单
设置一个等长的双向链表
然后给一个头指针，一个尾指针
遍历L，将L中2N+1位置的数从新链表的头指针向后插
将L中2N位置的的数中新链表的尾指针向前插
时间复杂度为O（n)
实现太容易了，就不详细说了
如有疑问，请追问。