求链表的倒数第m个元素（递归 / 双指针）

链表的声明

typedef struct Node *PtrToNode;
struct Node {
    ElementType Data; /* 存储结点数据 */
    PtrToNode   Next; /* 指向下一个结点的指针 */
};
typedef PtrToNode List; /* 定义单链表类型 */

#define ERROR -1

回溯 （递归）

 不太好的地方就是要用到全局变量, 因为函数签名已经被定下来了。

int key = 1;
ElementType Find( List L, int m ) {
    if(L->Next == NULL) {
        if(key == m) return L->Data;
        return ERROR;
    }
    int ans = Find(L->Next, m);
    key++;
    if(key == m) return L->Data;
    return ans;
}

 

先后指针

// 双指针技巧：先后指针
// 一个指针先走 k 步，然后慢指针和快指针一起走最终走到最后
// 慢指针走了 n - k 步

ElementType Find( List L, int m ) {
    List fir, sec;
    fir = sec = L->Next;
    while(fir) {
        if(!m) sec = sec->Next;
        else m--;
        fir = fir->Next;
    }
    if(m) return ERROR;
    return sec->Data;
}