C -使用单遍从链表中获取最后第三个节点

Question

我有一个单独的链接列表10 => 16 => 9 => 6 => 4 => 11 => 18 => 17 => 7 => 8

我没有给出(N)即节点数

我想用单次传递从上面的链接列表中获得第三个最后一个元素。我需要C代码。

Answer 1

由于op已经"得到它"，请注意，只能使用一个指向node的指针:

node *thirdtolast(node * list){
    node *pnode = list;
    if(pnode == NULL || pnode->next == NULL || pnode->next->next == NULL)
        return pnode;
    while(pnode->next->next->next != NULL)
        pnode = pnode->next;
    return pnode;
}

使用两个指针会更通用、更高效:

node *thirdtolast(node * list){
    node *pend = list;
    node *pnode = list;
    int i;
    for(i = 0; i < 3; i++){
        if(pend == NULL)
            return list;
        pend = pend->next;
    }
    while(pend != NULL){
        pend  = pend->next;
        pnode = pnode->next;
    }
    return pnode;
}