单链表：数据结点是单向排列的。
一个单链表结点，其结构分为两部分：数据域和指针域（用来存储其直接后继的地址）。例如：
typedef struct node{ char name[20]; struct node * next; }student;上述代码定义了一个单链表的结点，其中字符型数组char name[20]用来存储姓名。指针*link是一个用来存储其直接后继的指针。单链表中每个结点的地址是存储在其前驱结点的next域中，而开始结点无前驱，故应设头指针head指向其开始结点。
链表由头指针唯一确定，单链表可以用头指针的名字来命名。
求单链表倒数第k个节点：
常规做法：
先遍历一次链表求出链表长度n，链表的倒数第k个节点即正数的第（n-k+1）个，但是这样需要遍历两次链表。
遍历一次链表的思路：
1、定义两个指针p1和p2均指向链表头指针，p1先遍历链表，走（k-1）步，p2保持不变。
2、从第k步开始，同时移动两个指针，始终保持两个指针的距离为（k-1）。当p1到链表最后一个指针时，p2指向的恰好是链表倒数第k个节点。
代码实现：
#include <iostream> #include <malloc.h> using namespace std; typedef struct node{ int data; struct node *next; }node; /* * 遍历一遍就得到单链表的中间结点的方法 * 思想：两个指针，一个每次走一步，另一个每次走两步，两步走完的时候，一步的就是结果 */ int getCenterNode(node *head) { if(head -> next == NULL)//链表为空 return -1; node* temp = head->next; node* twoTemp = head->next;//最开始两个指针应该指向第一个有数据的节点。head里面没有存储数据 while(twoTemp -> next != NULL && twoTemp -> next -> next != NULL) { temp = temp -> next; twoTemp = twoTemp -> next ->next; } return temp -> data;//偶数个节点时，返回前一个节点的值 } void displayList(node *head) { cout << "List:"<< endl; node *p = head -> next; //node *p = head; while(p != NULL){ cout << p -> data <<" "; p = p-> next; } cout << endl; } /*求链表倒数第k个节点*/ node* kthNode(node *head,int k) { node * p1,*p2; p1 = head -> next;//链表的第一个有数据的节点 p2 = head -> next; for(int i = 1; i < k && p2->next != NULL; i++){ p2 = p2->next; } if(p2 -> next == NULL) return NULL; while(p2->next){//不是while(p2),否则会多向后挪动一个 p1 = p1 -> next; p2 = p2 -> next; } return p1; } int main() { node *head, *tmp; int i; head = (node*)malloc( sizeof(node)); head -> next = NULL; for(i = 1; i < 9; i++){//头插法，头指针没有数据，即head里面没有数据。所以输出数据的时候从head-> next->data开始 tmp = (node*)malloc(sizeof(node)); tmp -> data = i; tmp -> next = head -> next; head -> next = tmp; } displayList(head); cout<<getCenterNode(head)<<endl; node *p1 = kthNode(head, 4); cout << p1 -> data<<endl; return 0; }