程序员面试100题(算法)之查找链表中倒数第k个节点(含单向链表的创建和打印)
// 程序员面试100题(算法)之查找链表中倒数第k个节点#include "stdafx.h"#include<iostream>using namespace std;struct LinkNode{int value;LinkNode *next;};LinkNode *FindKNode(LinkNode *headNode, int k){if(NULL == headNode)return NULL;LinkNode *previous, *post;previous = post = headNode;int i = 1;while(i < k){post = post->next;i++;}while(NULL != post->next){previous = previous->next;post = post->next;}return previous;}LinkNode *CreateLink(LinkNode *headNode, int &length){int data = 0;LinkNode *previous, *post;if(NULL == headNode){cin >> data;if(-1 == data)return NULL;headNode = (LinkNode*)malloc(sizeof(LinkNode));if(headNode){headNode->value = data;headNode->next = NULL;length++;}else{cout << "No space" <<endl;}}previous = post = headNode;cin >> data;while(data != -1){post = (LinkNode*)malloc(sizeof(LinkNode));if(post){post->value = data;post->next = NULL;previous->next = post;previous = post;length++;}else{cout << "No space" << endl;}cin >> data;}return headNode;}void printLink(LinkNode *headNode){LinkNode *p = headNode;while(p){cout << p->value << "\t";p = p->next;}cout << endl;}int _tmain(int argc, _TCHAR* argv[]){int length = 0;LinkNode *headNode = NULL;headNode = CreateLink(headNode, length);printLink(headNode);int k = 0;cout << "Please input k:" << endl;cin >> k;if(k < length+1 && k > 0){LinkNode *kNode = NULL;kNode = FindKNode(headNode, k);cout << kNode->value << endl;}else{cout << "Please input right k" << endl;}return 0;}