【C/C++练习题】链表中倒数第k个结点

《剑指Offer》面试题22：链表中倒数第k个结点

1 题目

输入一个链表，输出该链表中倒数第k个结点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾结点是倒数第1个结点。例如一个链表有6个结点，从头结点开始它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个结点是值为4的结点。

2 分析

1. 设置两个指针p1 p2指向链表头节点，
2. 移动p2 (k-1)个长度，使得*p1相对*p2为"倒数第k个节点"
3. 同时移动p1 p2 ,使p2指向尾节点，返回*p1

另外，还要考虑对特殊情况的处理，比如输入头节点指针为空、k小于等于0、k大于链表中节点的总个数。。

3 代码

      #include "iostream"
      #include "cstdlib"
      using namespace std;
      //问题：寻找链表中倒数第k个节点(从1开始计数)
      typedef struct node
      {
     	int m_nValue;
      	node* m_pNext;
      }ListNode;
      ListNode* Tail_to_find(ListNode* pHead, int k);
      void Print_list_node(ListNode* pHead);
      void test01()
      {
      	ListNode* pHead  = NULL;
          ListNode* pNode1 = NULL;
          ListNode* pNode2 = NULL;
          ListNode* pNode3 = NULL;
          ListNode* pThis = NULL;
          pHead = (ListNode*)malloc(sizeof(ListNode));
          pNode1 = (ListNode*)malloc(sizeof(ListNode));
          pNode2 = (ListNode*)malloc(sizeof(ListNode));
          pNode3 = (ListNode*)malloc(sizeof(ListNode));
          pThis = (ListNode*)malloc(sizeof(ListNode));
     	if (pHead == NULL || pNode1 == NULL || pNode2 == NULL || pNode3 == NULL || pThis == NULL)
      	{
      		cout << "malloc fail" << endl;
     		return ;
      	}
      	pHead->m_nValue = 0;
      	pHead->m_pNext  = pNode1;
      	pNode1->m_nValue = 1;
      	pNode1->m_pNext  = pNode2;
      	pNode2->m_nValue = 2;
      	pNode2->m_pNext  = pNode3;
      	pNode3->m_nValue = 3;
      	pNode3->m_pNext  = NULL;
       	cout << "list:";
      	Print_list_node(pHead);		//打印链表节点信息
      	pThis = Tail_to_find(pHead, 1);
     	if (pThis != NULL)
      		cout << "k = 1, value = " << pThis->m_nValue << endl;
     	else
      		cout << "k = 1, input error" << endl;
      	pThis = Tail_to_find(pHead, 2);
     	if (pThis != NULL)
      		cout << "k = 2, value = " << pThis->m_nValue << endl;
     	else
      		cout << "k = 2, input error" << endl;
      	pThis = Tail_to_find(pHead, 4);
     	if (pThis != NULL)
      		cout << "k = 4, value = " << pThis->m_nValue << endl;
     	else
      		cout << "k = 4, input error" << endl;
      	pThis = Tail_to_find(pHead, 0);
     	if (pThis != NULL)
      		cout << "k = 0, value = " << pThis->m_nValue << endl;
     	else
      		cout << "k = 0, input error" << endl;
      	pThis = Tail_to_find(pHead, 100);
     	if (pThis != NULL)
      		cout << "k = 100, value = " << pThis->m_nValue << endl;
     	else
      		cout << "k = 100, input error" << endl;
      }
      int main(int argc, char const *argv[])
      {
     	test01();
     	return 0;
      }
      //功能：反向查找链表
      //输入：pHead 首节点指针， k 节点总数
      //返回：链表中倒数第k个节点的指针
      ListNode* Tail_to_find(ListNode* pHead, int k)
       {
      	//1.输入参数的合法性
      	if ((NULL == pHead) || (k <= 0))
       	{
      		return NULL;
       	}
      	//2.使p1指向第1个节点，p2指向第k个节点
       	ListNode* p1 = pHead;
       	ListNode* p2 = pHead;
      	for (int i = 0;i < k-1;i++)
       	{
      		if (p2->m_pNext != NULL)
       		{//没有达到尾部
       			p2 = p2->m_pNext;
       		}
      		else
       		{//特殊情况：k大于链表中节点总数
      			return NULL;
       		}
       	}
      	//3.同时移动p1 p2,使p2指向尾节点
      	while (p2->m_pNext != NULL)
       	{
       		p1 = p1->m_pNext;
       		p2 = p2->m_pNext;
       	}
      	//4.返回p1指针
      	return p1;
       }
      //功能：打印链表所有节点
      //输入：pHead 头节点地址
      //返回：无
      void Print_list_node(ListNode* pHead)
      {
     	if (pHead != NULL)
      	{
     		while (pHead->m_pNext != NULL)
      		{
      			cout << pHead->m_nValue << ",";	//打印节点信息
      			pHead = pHead->m_pNext;
      		}
      		cout << pHead->m_nValue << endl;	//打印尾节点
      	}
      }
  
 

4 运行结果

文章来源: blog.csdn.net，作者：hinzer，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/feit2417/article/details/98715732