C -如何在链表中跟踪我的尾节点

Question

如何跟踪尾部节点以便快速返回其值?这就是我如何创建我的列表到目前为止，但我想写一个函数，可以返回最后一个节点，并从列表中删除它。不太确定从哪里开始

typedef struct node_t{
    int val;
    struct node_t *next;
}node_t;
int main(int argc, char *argv[])
{
    int input;
    node_t *list;
    list = NULL;
    list = push(1,list);
    list = push(2,list);
    list = push(3,list);
    return 0;
}

node_t *push(int input, node_t *list)
{
    if(list == NULL)
    {
        list = makeStack(input, list);
        return list;
    }
    else
    {
        list->next = push(input,list->next);
    }
    return list;
}

Answer 1

基本上有两种方法:

你可以使用如下函数计算最后一个节点的指针:

node_t * find_last( node_t * ptr )
{
 /* is this node last? */
 if ( ptr->next == NULL )
  return ptr;
 /* let's travel to last node */
 do
  ptr = ptr->next;
 while ( ptr->next != NULL );
 /* and then return it */
 return ptr;
}

但是对于大列表，这个函数可能开销很大。

第二种方法只需要在某种基结构中缓存最后一个指针的值。

typedef struct
{
 node_t * first;
 node_t * last;
} linked_list_t;