剑指offer之打印链表的倒数第N个节点的值

1 问题

打印链表的倒数第N个节点的值，（要求能只能便利链表一次）

比如链表如下，打印倒数第三个值就是4

1-> 2-> 3-> 4-> 5-> 6

2 思路

既然只要只能遍历一次，我们可以这样思考，比如我们要得到倒数第三个，那么它和尾巴的长度就是3，我们可以这一节距离一直往左边移动，那么移动最左边的话，他们的开始是1，尾巴是3，所以我们搞2个指针进行移动就行，如下过程，就可以得到4.

1   ->   2   ->   3   ->   4   ->   5  ->  6 

start

end    

1   ->   2   ->   3   ->   4   ->   5  ->  6 

start               end

1   ->   2   ->   3   ->   4   ->   5  ->  6 

                                start              end

无非就是上面的逆过程，我们用代码实现就行

3 代码实现

  

   

    

     

    
    

     

      #include <iostream>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      using namespace std;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      typedef struct node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	int value;
     
    
   

    

     

    
    

     
	struct node *next;
     
    
   

    

     

    
    

     

      } Node;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void printN(Node *head, int n)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	if (head == NULL || n <= 0)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		std::cout << "head is NULL or n <= 0" << std::endl;
     
    
   

    

     

    
    

     
		return;	
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      	Node *start = head;
     
    
   

    

     

    
    

     

      	Node *end = head;
     
    
   

    

     

    
    

     
	//这里需要考虑n的大小长度是否大于链表长度
     
    
   

    

     

    
    

     
	//我们不能直接遍历链表得到链表大小然后和n比较
     
    
   

    

     

    
    

     
	//那我们就用start->next != NULL来判断也行
     
    
   

    

     

    
    

     
	for (int i = 0; i < n - 1; ++i)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		if (start->next != NULL)
     
    
   

    

     

    
    

     

      			start = start->next;
     
    
   

    

     

    
    

     
		else
     
    
   

    

     

    
    

     

      		{
     
    
   

    

     

    
    

     
			std::cout << "the value of n is more than larger the length of list" << std::endl;
     
    
   

    

     

    
    

     
			return;
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	while (start->next != NULL)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		end = end->next;
     
    
   

    

     

    
    

     

      		start = start->next;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	std::cout << "the value is: " << end->value << std::endl;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

      	Node *head = NULL;
     
    
   

    

     

    
    

     

      	Node *node1 = NULL;
     
    
   

    

     

    
    

     

      	Node *node2 = NULL;
     
    
   

    

     

    
    

     

      	Node *node3 = NULL;
     
    
   

    

     

    
    

     

      	head = (struct node*)malloc(sizeof(Node));
     
    
   

    

     

    
    

     

      	node1 = (struct node*)malloc(sizeof(Node));
     
    
   

    

     

    
    

     

      	node2 = (struct node*)malloc(sizeof(Node));
     
    
   

    

     

    
    

     

      	node3 = (struct node*)malloc(sizeof(Node));	
     
    
   

    

     

    
    

     
	if (head == NULL || node1 == NULL || node2 == NULL || node3 == NULL)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		std::cout << "malloc fail" << std::endl;
     
    
   

    

     

    
    

     
		return -1;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      	head->value = 0;
     
    
   

    

     

    
    

     

      	head->next = node1;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	node1->value = 1;
     
    
   

    

     

    
    

     

      	node1->next = node2;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	node2->value = 2;
     
    
   

    

     

    
    

     

      	node2->next = node3;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      	node3->value = 3;
     
    
   

    

     

    
    

     

      	node3->next = NULL;
     
    
   

    

     

    
    

     
		
     
    
   

    

     

    
    

     

      	printN(head, 3);
     
    
   

    

     

    
    

     
	free(head);
     
    
   

    

     

    
    

     
	free(node1);
     
    
   

    

     

    
    

     
	free(node2);
     
    
   

    

     

    
    

     
	free(node3);
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     
	
     
    
   

    

     

    
    

     

      }
     
    
  
 

4 运行结果

the value is: 1
 

5 总结

请记住，2个指针像一把梭子，那样在移动，是那么的美妙，所以当一个指针便利不了的时候，要记得用2个指针便利

然后还有类似的问题，比如求链表的中点，链表长度是奇数的时候，取中间的数字，如果链表长度是偶数的话，取中间的2个都行，我们依然用2个指针，一个走一步，一个走2步，当快的走完了的时候，慢的的走到中间了，切记。

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

原文链接：chenyu.blog.csdn.net/article/details/87480975