/*
设线性表L=（a1,a2,a3,...,an-2,an-1,an）,采用带头结点的单链表保存，设计一个空间复杂度为O(1)的
算法，得到L'=（a1,an,a2,an-1,a3,an-2...）
分析：
还是有一点复杂的，不过我们慢慢分析它。我们可以这样来操作，我们设置两个指针slow和fast，其中fast每次走两步，
slow每次走一步，当fast到达链尾时，slow刚好处于链表中间节点，之前我们学过链表逆置，接下来我们把slow后面的节点逆置，
链表就变成了（a1,a2,a3,...,an,an-1,an-2,...）,然后我们从中间开始遍历，依次将节点插入到前面节点后面，即可完成要求
*/
#include<stdio.h>
#include<stdlib.h>
typedef struct LNode
{
int value;
struct LNode *next;
}LNode,*Linklist;
Linklist list_TailInsert(Linklist &L)
{
L = (Linklist)malloc(sizeof(LNode));
LNode *head = L,*rear = L;
L->next = NULL;
L->value = NULL;
int x;
printf("请输入单链表结点的个数：");
scanf("%d",&x);
for(int i = 0; i < x; i++)
{
int value;
printf("请输入单链表第%d个结点的值：",i+1);
scanf("%d",&value);
LNode *s;
s = (Linklist)malloc(sizeof(LNode));
s->value = value;
s->next = NULL;
rear->next = s;
rear = s;
}
rear->next = NULL;
return L;
}
void Display(Linklist &L)
{
LNode *p = L->next;
while(p != NULL)
{
printf("%d ",p->value);
p = p->next;
}
printf("\n");
}
void reverse(LNode *L)
{
LNode *pre =L,*p = L->next,*q;
L->next = NULL;
while(p != NULL)
{
q = p->next;
p->next = pre->next;
pre->next = p;
p = q;
}
}
void crossTheLink(Linklist &L)
{
LNode *fast = L->next,*slow = L->next,*mid,*p;
while(fast->next != NULL && fast != NULL)
{
slow = slow->next;
fast = fast->next->next;
}
mid = slow;
reverse(mid);
Display(mid);
slow = mid->next;
fast = L->next;
mid->next=NULL;
while(slow != NULL)
{
p = slow->next;
slow->next = fast->next;
fast->next = slow;
printf("\nslow-value=%d ",slow->value);
printf("fast->value=%d\n",fast->value);
slow = p;
fast = fast->next->next;
}
}
int main()
{
Linklist L1;
list_TailInsert(L1);
Display(L1);
crossTheLink(L1);
Display(L1);
return 0;
}
