【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