程序员面试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; } // 程序员面试100题(算法)之查找链表中倒数第k个节点 #include "stdafx.