真题

2009年

链表：
暴力解：枚举                                时间:O(n^2) 空间：O(1)
暴力解：递归+链表遍历                       时间:O(n)   空间：O(n)
暴力解：数组保存所有链表结点                时间：O(n)  空间：O(n)
较优解（也是最优）：遍历链表两次            时间：O(n)  空间：O(1)
最优解：链表操作技巧——前后双指针           时间：O(n)  空间：O(1)

暴力解：枚举

1. 两层循环，外层是遍历i，内层是找到倒数第i个元素，比如上一轮查找到倒数第i-1个结点是q，那下一轮当p->link==q时p就是倒数第i个结点。
2. 算法如下：

ing ans(node* list,int k){
    node* p,q=null  //q=null 是倒数第0个结点
    for(int i=1;i<k;i++)
    {
        p=list->link;
        if(q==p)
        return 0;    //找不到第k个结点
        while(p->link!=q)
        p=p->link;  //p最终是倒数第i个结点
        q=p;
    }
    cout<<p->data;  //输出倒数第k个结点的值
    return 1; 

}

3. 时间复杂度：O(n^2) 空间复杂度：O(1)

暴力解：递归+链表遍历

1. 递归调用一个一个访问节点，全局变量t表示此时访问的结点是倒数第几个结点，如果t==k说明是倒数第k个结点，输出该结点。
2. 算法如下：

int t=0; //t表示当前访问的是倒数第k个节点
void find(node* p,int k)
{
    if(p==null) return ;
    find(p->link,k)
    t++;
    if(t==k)
    cout<<p->data;  //输出倒数第k个元素
}
int ans(node* list,int k){
    find(list->link,k);
    if(t<k)
      return0;
    return1;
}

3.时间复杂度：O(n) 空间复杂度：O(n)

暴力解：数组保存所有链表节点
1. 遍历链表，将所有结点都存放在数组中，最后输出数组中倒数第k个元素即可。
2. 算法如下

int ans(node* list,int k){
    node* A[maxn];      //结点数组
    node* p=list->link;     //正在遍历的结点
    int n=0;        //数组中结点个数
    while(p!=null){
        A[n++]=p;
        p=p->link;
    }
    if(n<k)
      return 0;
    coutA[n-k]->data;       //输出倒数第k个元素的值
    return 1;
}

3.时间复杂度：O(n) 空间复杂度：O(n)

较优解(也是最优):遍历链表两次

1. 要找到倒数第k个结点，但链表不能回退，所以需要知道他是从前往后数第t个结点（不算头结点），t=n-k+1，n是总结点数，那我们只需要先遍历一次链表求出n，然后再遍历一次链表找到第t个结点。
2. 算法如下：

int ans(node* list,int k){
    node* p=list->link;
    int t,n=0;
    while (p!=null){
        n++;
        p=p->link;
    }
    t=n-k+1;
    if(t<0)
        return 0;
    p=list;
    for(int i=0;i<t;i++)
        p=p->link;
    cout<<o->data;          //输出倒数第k个元素
    return 1;
}

3.时间复杂度：O(n) 空间复杂度：O(1)

最优解：链表操作技巧——前后双指针

1. 始时设置两个指针p和q都指向头结点，q指针先后移k次，若此过程中q指向了null则查找失败，返回0。然后将p和q同时后移，直到q指向null为止，因为p和q直接相差k次移动，所以此时p一定指向倒数第k个结点，输出p，返回1.
2. 算法如下：

int ans(node* list,int k){
    node* p=q=list;
    for(int i=0;i<k;i++){
        q=q->link;
        if(q==null)
          return 0;
    }
    while(q!=null){
        p=p->link;
        q=q->link;
    }
    cout<<p->data; //输出倒数第k个元素的值
    return 1;
}

3.时间复杂度：O(n) 空间复杂度：O(1)