链表【6】完结篇）

回文链表（快慢指针+翻转后半部分的链表）

#include<stdio.h>
const int N=1005;
int n,first,firstid;
using namespace std;
struct node
{int data;int next;
} ;
node lnode[N]; void readin()
{for(int i=0;i<n;i++){	int idtemp;scanf("%d",&idtemp);scanf("%d %d",&lnode[idtemp].data,&lnode[idtemp].next);}}
//
//void readout()
//{	int temp=firstid;
//while(temp!=-1)
//{printf("%d %d %d\n",temp,lnode[temp].data,lnode[temp].next );temp=lnode[temp].next ;
//}//}
void deletex(int pre)
{lnode[pre].next=lnode[lnode[pre].next].next;
}
int main()
{scanf("%d %d",&n,&firstid);int tgt;
//    int itern=first;
//	scanf("%d",&tgt);readin();int  cur_s=firstid,next_f;int  cur_f=firstid,next_s;int count=0;//快慢指针 
while(lnode[lnode[cur_f].next].next !=-1 && lnode[cur_f].next != -1)
{//printf("%d %d\n",cur_f,cur_s);
next_f=lnode[cur_f].next; cur_f=next_f;
next_f=lnode[cur_f].next; cur_f=next_f;
//if((count%2)) 
//{//printf("count%d\n",count);
next_s=lnode[cur_s].next; cur_s=next_s;
//}
count++;}//printf("%d",count);//反转链表 ，翻转slow下一位至-1
//	int headm=lnode[cur_s].next;int cur=lnode[cur_s].next;int pre=-1;int next;while(cur!=-1){next=lnode[cur].next;lnode[cur].next =pre;pre=cur;cur=next;} int cur1=firstid;cur=pre;bool flag=0;int xunhuan=0;while(cur!=-1 && xunhuan<100){//printf("%d %d %d %d",cur,cur1,lnode[cur].data ,lnode[cur1].data);if(lnode[cur].data !=lnode[cur1].data) flag=1;if(flag)break;cur=lnode[cur].next ;cur1=lnode[cur1].next ;xunhuan++;}printf(flag?"No":"Yes");}

翻转位置是slow。next

倒数第k个元素

块指针出发k次后，让慢指针出发，然后一起走 

快指针到尽头，慢指针指向倒第k

#include<stdio.h>
const int N=1005;
int n,first,firstid;
using namespace std;
struct node
{int data;int next;
} ;
node lnode[N]; void readin()
{for(int i=0;i<n;i++){	int idtemp;scanf("%d",&idtemp);scanf("%d %d",&lnode[idtemp].data,&lnode[idtemp].next);}}
//
//void readout()
//{	int temp=firstid;
//while(temp!=-1)
//{printf("%d %d %d\n",temp,lnode[temp].data,lnode[temp].next );temp=lnode[temp].next ;
//}//}
void deletex(int pre)
{lnode[pre].next=lnode[lnode[pre].next].next;
}
int main()
{
int k;scanf("%d %d %d",&n,&firstid,&k);int tgt;
//    int itern=first;
//	scanf("%d",&tgt);readin();int  cur_s=firstid,next_f;int  cur_f=firstid,next_s;int count=1;//快慢指针 
while( count<k)
{//printf("%d %d\n",cur_f,cur_s);
next_f=lnode[cur_f].next; cur_f=next_f;//}
count++;}
while(lnode[cur_f].next != -1)
{next_f=lnode[cur_f].next; cur_f=next_f;next_s=lnode[cur_s].next; cur_s=next_s;}
printf("%d %d %d",cur_s,lnode[cur_s].data,lnode[cur_s].next);}