面试题13：链表中倒数第k个结点

思路：设置两个指针，一个慢指针pSlow，一个快指针pFast，快指针先走k-1步，接着两个指针同时走，当快指针到达链表的尾部，慢指针恰好指向倒数第k个结点。

特殊情况：当k大于链表长度，则返回头结点。

代码：

#include "stdafx.h"   
#include <iostream>   
using namespace std;  
  
struct ListNode  
{  
    int m_nValue;  
    ListNode *m_pNext;  
};  
  
ListNode *FindKthToTail(ListNode *pHead, int k)  
{  
    if (pHead == NULL || k == 0)  
    {  
        return NULL;  
    }  
  
    ListNode *pSlow = pHead;  
    ListNode *pFast = pHead;  
    int i = 1;  
    while (i < k)  
    {  
       pFast = pFast->m_pNext;  
       if (pFast == NULL)  
       {  
           cout << "k = " << k << "大于链表长度！" << endl;  
           break;  
       }  
       i++;  
    }  
  
    if (pFast != NULL)  
    {  
        while (pFast->m_pNext != NULL)  
        {  
            pSlow = pSlow->m_pNext;  
            pFast = pFast->m_pNext;  
        }  
    }  
    return pSlow;  
}  
  
//创建一个链表，输入从头到尾结点的值，输入-1表示结束   
void CreateList(ListNode *& pHead)  
{     
    ListNode *pListNode = NULL;  
    ListNode *pCurLastNode = NULL;  
    bool isHead = true;  
  
    while (1)  
    {  
        if (isHead)  
        {     
            pHead = new ListNode();  
            cin >> pHead->m_nValue;  
            pHead->m_pNext = NULL;  
            isHead = false;  
            pCurLastNode = pHead;  
        }  
        else  
        {  
            pListNode = new ListNode();  
            cin >> pListNode->m_nValue;  
            if (pListNode->m_nValue == -1)  
            {  
                break;  
            }  
            pListNode->m_pNext = NULL;  
            pCurLastNode->m_pNext = pListNode;  
            pCurLastNode = pListNode;     
        }             
    }  
}  
  
//从头到尾打印链表   
void PrintList(ListNode *&pHead)  
{  
    if (pHead != NULL)  
    {  
        ListNode *pCur = pHead;  
        while (pCur != NULL)  
        {  
            cout << pCur->m_nValue << " ";  
            pCur = pCur->m_pNext;  
        }  
        cout << endl;  
    }  
    else  
    {  
        cout << "链表为空！" << endl;  
    }  
}  
  
int _tmain(int argc, _TCHAR* argv[])  
{  
    ListNode *pListHead = NULL;  
    CreateList(pListHead);  
    PrintList(pListHead);  
    ListNode *pKthNodeToTail = FindKthToTail(pListHead, 6);  
    cout << pKthNodeToTail->m_nValue << endl;  
    return 0;  
}  
#include "stdafx.h"
#include <iostream>
using namespace std;

struct ListNode
{
	int m_nValue;
	ListNode *m_pNext;
};

ListNode *FindKthToTail(ListNode *pHead, int k)
{
	if (pHead == NULL || k == 0)
	{
		return NULL;
	}

	ListNode *pSlow = pHead;
	ListNode *pFast = pHead;
	int i = 1;
	while (i < k)
	{
       pFast = pFast->m_pNext;
	   if (pFast == NULL)
	   {
		   cout << "k = " << k << "大于链表长度！" << endl;
		   break;
	   }
	   i++;
	}

	if (pFast != NULL)
	{
		while (pFast->m_pNext != NULL)
		{
			pSlow = pSlow->m_pNext;
			pFast = pFast->m_pNext;
		}
	}
	return pSlow;
}

//创建一个链表，输入从头到尾结点的值，输入-1表示结束
void CreateList(ListNode *& pHead)
{	
	ListNode *pListNode = NULL;
	ListNode *pCurLastNode = NULL;
	bool isHead = true;

	while (1)
	{
		if (isHead)
		{	
			pHead = new ListNode();
			cin >> pHead->m_nValue;
			pHead->m_pNext = NULL;
			isHead = false;
			pCurLastNode = pHead;
		}
		else
		{
			pListNode = new ListNode();
			cin >> pListNode->m_nValue;
			if (pListNode->m_nValue == -1)
			{
				break;
			}
			pListNode->m_pNext = NULL;
			pCurLastNode->m_pNext = pListNode;
			pCurLastNode = pListNode;	
		}			
	}
}

//从头到尾打印链表
void PrintList(ListNode *&pHead)
{
	if (pHead != NULL)
	{
		ListNode *pCur = pHead;
		while (pCur != NULL)
		{
			cout << pCur->m_nValue << " ";
			pCur = pCur->m_pNext;
		}
		cout << endl;
	}
	else
	{
		cout << "链表为空！" << endl;
	}
}

int _tmain(int argc, _TCHAR* argv[])
{
	ListNode *pListHead = NULL;
	CreateList(pListHead);
	PrintList(pListHead);
	ListNode *pKthNodeToTail = FindKthToTail(pListHead, 6);
	cout << pKthNodeToTail->m_nValue << endl;
	return 0;
}

补充：软件开发 , C++ ,

上一个：面试题14：反转链表
下一个：面试题12：调整数组顺序使奇数位于偶数前