《剑指offer》面试题15—输出链表中倒数第n个结点

题目：如题，且从1开始计数。

思路：要求只遍历一遍链表：设置两个指针，一个先走n步后另一个开始同步后移，当快指针已经到链表尾时慢指针正好到要输出的结点。

注意：本题思路比较好想到，主要考察的是代码的鲁棒性！要判断输入参数是否尾空指针，以及n是否有效。

  1 #include <iostream>
  2 using namespace std;
  3 
  4 
  5 class Node
  6 {
  7 public:
  8     Node(int v, Node* n)
  9     {val = v;
 10     next = n;}
 11     ~Node(){}
 12     int val;
 13     Node* next;
 14 };
 15 Node * phead = NULL;
 16 
 17 void AddNode(int val)
 18 {
 19     Node* pnode = new Node(val,NULL);
 20     //Node one_node(val,NULL); 这里有大bug！如果这样写，在函数退出时自动调用析构函数！链表就乱了！
 21     if(phead == NULL)
 22     {
 23         phead = pnode;
 24     }
 25     else
 26     {
 27         Node* p = phead;
 28         while(p->next != NULL)
 29         {
 30             p = p->next;
 31         }
 32         p->next = pnode;
 33     }
 34 }
 35 void PrintLink()
 36 {
 37     Node* p = phead;
 38     while(p != NULL)
 39     {
 40         int temp = p->val;
 41         cout<<temp<<endl;
 42         p = p->next;
 43     }
 44 }
 45 
 46 Node* FindNthFromTail(int n) //n >= 1, linklist counts from 1 to n
 47 {
 48     Node* pfast;
 49     Node* pslow;
 50     if(phead == NULL)
 51     {
 52         cout<<"Empty Link!"<<endl;
 53         return NULL;
 54     }
 55     else if(n<=0)
 56     {
 57         cout<<"Illegal N!"<<endl;
 58         return NULL;
 59     }
 60     else
 61     {
 62         pfast = phead;
 63         pslow = phead;
 64         for(int i=1; i<n; i++)
 65         {
 66             if(pfast->next != NULL)
 67                 pfast = pfast->next;
 68             else
 69                 {
 70                     cout<<"Illegal N!"<<endl;
 71                     return NULL;
 72                 }
 73         }
 74         while(pfast->next != NULL)
 75         {
 76             pslow = pslow->next;
 77             pfast = pfast->next;
 78         }
 79         return pslow;
 80     }
 81 }
 82 
 83 int main()
 84 {
 85     int val,n,flag;
 86     Node* pfind;
 87     cin>>val;
 88     while(val != 0)
 89     {
 90         AddNode(val);
 91         cin>>val;
 92     }
 93     PrintLink();
 94     cout<<"Input the node number you want to find form tail:"<<endl;
 95     cin>>n;
 96     pfind = FindNthFromTail(n);
 97     if(pfind)
 98     {
 99         cout<<"Find!"<<endl<<"The key value is:"<<pfind->val<<endl;
100     }
101     return 0;
102 }

View Code

举一反三：

1.求链表的中间结点：两个指针，一个每次两步，另一个每次一步。当快指针到链表尾时满指针正好到中间。

2.判断一个链表是否形成环结构：两个指针，一个每次两步，另一个每次一步。如果快指针遇到NULL了说明到链表尾了，肯定没有环；如果有环，由于快指针每次都比慢指针多走一步，快指针最终会追上慢指针（注意这里快指针不会跳过慢指针而不相遇，因为每次只多一步）