请教一道数据结构的算法题算法具体描述如下： 设以带头结点的双向循环链表L=（a1,a2,....,an).试写一个时
设以带头结点的双向循环链表L=（a1,a2,....,an).试写一个时间复杂度为O（n)的算法，将L改造成L=（a1,a3,...an,...,a4,a2)。要求写出你...
设以带头结点的双向循环链表L=（a1,a2,....,an).试写一个时间复杂度为O（n)的算法，将L改造成L=（a1,a3,...an,...,a4,a2)。要求写出你的算法思想。要求用C语言写程序
展开
2个回答
展开全部
有两种思想供参考：（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了。
程序交给你来写吧，应该不太难。
先来说说整体思想，我们可以发现序号为奇数的元素的前后相对位置未变，只是偶数位置有变化。这样的话，我们可以将偶数按序号逆序（由大到小）插入到链表尾部。考虑到时间复杂度问题，在搜索偶数的过程中，可以先找到最大的偶数序号+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了。
程序交给你来写吧，应该不太难。
已赞过
已踩过<
评论
收起
你对这个回答的评价是？
推荐律师服务：
若未解决您的问题，请您详细描述您的问题，通过百度律临进行免费专业咨询
