题解 | #输出单向链表中倒数第k个结点#

链表的结构真恶心啊。

我一个只学过一点点C的人就嗯模仿，数据流转使人死亡。

笑死了，连定义头指针都不会。

这道题没什么难点，如果前面的题目都刷了，这就是一个简单的寻址问题。

处理数组的思想完全可以套用在这。

就是链表的调用费了许多时间。

创建链表每次只能增加一个结点（即写入一个数据指向下一个位置），属实难顶。（我说的可能不对，因为之前没有学过，所以是从代码中推测的，）

插入移动也每次只能移动一个，这一点和数组的去重操作有一些相似之处。

不要忘记释放内存。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


int N,val;
int count=0;
int k=0;


struct  list_node//创建链表结构
{
	int m_nKey ; 
	struct list_node *m_pNext ;
};
 
typedef struct list_node list_single ; 	


list_single *create_list_node(int data)//创建链表和结点
{
	list_single *node = NULL ;//定义头指针
	node = (list_single *)malloc(sizeof(list_single));//分配内存空间
	if(node == NULL){
		printf("malloc fair!\n");
	}
	memset(node,0,sizeof(list_single));//reset
	node->m_nKey = data;//给链表结点数据赋值
	node->m_pNext = NULL ;//链表指针域指向空
  //  free(node);
	return node ;
}

list_single *tailnode(list_single* headNote,int m_nKey)//尾插结点
{
    list_single *new_node=create_list_node(m_nKey);//将要尾插的新链表结构
    
    list_single *insert_pMove=headNote;//获取当前结点位置，访问头结点
    
    while(insert_pMove->m_pNext != NULL)//判断是否为最后一个结点
    {
        insert_pMove = insert_pMove->m_pNext;//如果不是，移动到下一个结点
    }
    
    
    insert_pMove->m_pNext = new_node;//如果是，将数据插入尾部
    
    count++;//尾插1，结点加一
    
    return 0;
    
}


/*list_single *fowardnode(list_single* headNote,int m_nKey)//头插结点
{
    list_single *new_node=create_list_node(m_nKey);//将要尾插的新链表结构
    
    list_single *head_pMove=headNote;//获取当前结点位置，访问头结点
       
    new_node->m_pNext  = head_pMove->m_pNext;//将新结点的下一个结点设置为原来结点的下一个结点
    
    head_pMove->m_pNext = new_node;//原来的头结点的下一个结点设置为新插入的头结点
    
}*/



list_single *findnode(list_single* headNode, int k)//寻找倒数第k结点
{
     list_single *find_pMove= headNode;//确定搜索开始的位置
    if(count>=k)
    {
        
     for(int i=0;i<(count-k+1);i++)//一直搜寻到倒数第k个
         
     {   
         
      find_pMove = find_pMove->m_pNext;    //如果没搜到边界，链表指向下一个位置。      
     
     }  
        
      return find_pMove->m_nKey;  //返回链表中的值
    }
    
    else                //没有或者长度不够则返回NULL
        return NULL;
    
}






int main(void)
{
  list_single* headNode=create_list_node(N);//创建头结点
  while((scanf("%d\n",&N))!=EOF)
  {
   
    for(int i=0;i<N;i++)
    {
        
        scanf("%d \n",&val);//每次收入一个数据写入链表
        tailnode(headNode,val);//每次将新收入的数据尾插
    }
    
    scanf("%d\n",&k);
    printf("%d\n",findnode(headNode, k));//检索倒数第k个数据并输出
      
  }
    free(headNode);
}