#include
#include
#include
typedef int DataType;
typedef struct SListNode
{
DataType data;
struct SListNode* next;
}SListNode;
SListNode* BuyNode(DataType x)
{
SListNode* next = (SListNode*)malloc(sizeof(SListNode));
next->data = x;
next->next = NULL;
return next;
}
void PushBack(SListNode* & ppHead, DataType x)
{
if (ppHead == NULL)
{
ppHead = BuyNode(x);
}
else
{
SListNode* tail = ppHead;
while (tail->next != NULL)
{
tail = tail->next;
}
tail->next = BuyNode(x);
}
}
//查找单链表的倒数第k个节点,要求只能遍历一次
SListNode* FindLastKMiddle(SListNode* ppHead,DataType k)
{
SListNode* slow = ppHead;
SListNode* fast = ppHead;
while (fast !=NULL && k--)
{
fast = fast->next;
}
if (k > 0)
{
return NULL;
}
while (fast)
{
fast = fast->next;
slow = slow->next;
}
return slow;
}
void PrintSNodeList(SListNode* ppHead)
{
while (ppHead)
{
printf("%d->", ppHead->data);
ppHead = ppHead->next;
}
printf("\n");
}
void Test3()
{
SListNode* List = NULL;
PushBack(List, 1);
PushBack(List, 2);
PushBack(List, 3);
PushBack(List, 4);
PushBack(List, 5);
PrintSNodeList(List);
SListNode *ret = FindLastKMiddle(List, 4);
if (ret == NULL)
{
printf("该值不存在!\n");
}
else
{
printf("%d ", ret->data);
}
}
int main()
{
Test3();
system("pause");
return 0;
}