单链表逆置、删除等简单 *** 作

建立在上一篇文章 能够构建简单单链表的基础上的简单进阶篇

void reve(link *p)//将单链表逆置，要求不改变结点地址
{link *r=0,*q=0,*s=0;//通过头插法进行单链表的逆置
 r=p->next;
 q=r->next;
 s=q->next;
 r->next=NULL;
while(s!=0)
 {q->next=p->next;
 p->next=q;
 q=s;
 s=s->next;}
 q->next=p->next;
 p->next=q;
}

对于单链表的逆置是非常常见的一类问题，通常可以通过头插法进行循环，轻松的将指针依次变向。

void favg(link *p)//寻找单链表的中节点
{
  link *r=p;
  int i=1,j=1;
  while(r->next!=0)
  {
    r=r->next;
    i++;
  }
  r=p;
  if(i%2!=0)
  {while(j<=(i-1)/2)
  {
    r=r->next;
    j++;
  }
  printf("该单链数据表节点数为奇数,中节点为:%d",r->data);
  }
  else
  {
    while(j<=i/2)
  {
    r=r->next;
    j++;
  }
  printf("该单链数据表节点数为偶数,中节点为:%d,%d",r->data,r->next->data);
  }
}

对于单链表中节点，由于重新写的一个函数，需要对单链表遍历一次，数出总的节点数，然后分奇偶情况，再对单链表进行半遍历，输出中节点数据。

void fbackk(link *p,int k)//找单链表倒数第K个点
{
   link *r=p;
  int i=1,j=1;
  while(r->next!=0)
  {
    r=r->next;
    i++;
  }
  r=p;
  for(j;j<=(i-k);j++)
  {
    r=r->next;
  }
  printf("单链表倒数第%d节点的值为:%d",k,r->data);
}

 

void delbackk(link *p,int k)//删除单链表倒数第k个点
{
    link *r=p,*m=0,*n=0;
  int i=1,j=1;
  while(r->next!=0)
  {
    r=r->next;
    i++;
  }
  r=p;
  for(j;j<(i-k);j++)
  {
    r=r->next;
  }
  m=r->next;
  n=m->next;
  r->next=n;
}

删除倒数第k个节点数据。

int main()
{ link *L1;
  int i,k;
  printf("请输入单链表一的长度i:");
  scanf("%d",&i);
  printf("\n");
  L1=start(L1);
  printf("构建单链表L1\n");
  create(L1,i);
  print(L1); 
  reve(L1);
  printf("\n逆置后\n");
  print(L1); 
  printf("\n");
  favg(L1);
  printf("\n");
  printf("你要查找倒数第几个节点的数?\n");
  scanf("%d",&k);
  fbackk(L1,k);
  printf("\n");
  delbackk(L1,k);
  printf("删除倒数第%d个节点后\n",k);
  print(L1);
   return 0;
}

 最终代码运行结果（包括第一篇文章的部分代码）