考研数据结构（每日一题）day23

考研数据结构（每日一题）
题目：设线性表L=(a1,a2,a3,…,an-2,an-1,an)采用带头结点的单链表保存，请设计一个空间复杂度为O(1)且时间上尽可能高效的算法，重新排列L中的各节点，得到线性表L’=(a1,an,a2,an-1,a3,an-2,…)
算法图解：

算法思想：
L’是由L取第一个元素，再取倒数第一个元素，以此类推，依次合并而成的。为了方便链表后半段取元素，需要先将L后半段原地逆置（如图红色方框部分），题目中要求空间复杂度为O(1)，即不能用栈，否则每取最后一个结点都需要遍历一次链表。 算法详细步骤： 第一步：设置两个指针p、q，找出链表L的中间结点，指针p每次走一步，q每次走两步。当指针q到达链表尾部时，指针p刚好在链表的中间结点 第二步：将L的后半段结点原地逆置 第三步：从单链表前后两段中依次各取一个结点，按题目要求排列
完整代码：
typedef struct no

考研数据结构（每日一题）day23最先出现在Python成神之路。