如何跟蹤鏈表中的尾節點

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; 
} 

但隨着大名單的這個功能可能很昂貴。

第二種方法要求你簡單地緩存最後一個指針在某種「基」結構中的值。