C语言 使用指向起始节点的单个指针删除单个链表的最后一个节点

Delete the last node of a single linked list using the single pointer to start node

提问by arpita

Can I delete the last node using the below prototype in C -: int delete(struct node *head, int item)

我可以在 C 中使用以下原型删除最后一个节点吗？： int delete(struct node *head, int item)

Note-: The first argument here is a point to start node and not pointer to pointer to start node .

注意：这里的第一个参数是指向起始节点的指针，而不是指向起始节点的指针。

Thanks

谢谢

回答by Deepu

Yes. It is possible to delete the last node of a singly linked list, starting from the first node.

是的。可以从第一个节点开始删除单向链表的最后一个节点。

Try the following code,

试试下面的代码，

int delete(struct node *head)
{
  struct node *temp =head;
  struct node *t;
  while(temp->next != NULL)
  {
    t=temp;
    temp=temp->next;
  }
  free(t->next);
  t->next=NULL; 
}  

But if there is just a single element in your linked list, then after deleting that element your head pointer will still point to the now deleted memory location in the function from which you called the delete(). In such a case use the following version of delete().

但是如果链表中只有一个元素，那么在删除该元素后，您的头指针仍将指向调用delete(). 在这种情况下，请使用以下版本的delete().

struct node *delete(struct node *head)
{
  struct node *temp =head;
  struct node *t;
  if(head->next==NULL)
  {
    free(head);
    head=NULL;
  }
  else
  {
     while(temp->next != NULL)
     {
        t=temp;
        temp=temp->next;
     }
     free(t->next);
     t->next=NULL; 
  }    
  return head;
}

Call the function delete()as follows,

调用函数delete()如下，

head=delete(head);

回答by AnT

The answer depends on what exactly is meant by the question.

答案取决于问题的确切含义。

You can, of course, easily and safely delete the last element (= tail element of the list), if the list contains more than one element. Simply iterate to the element before the last, delete the last and update the nextpointer in new last element. Note that in that case the caller's headpointer will remain a perfectly valid pointer to a valid list.

当然，如果列表包含多个元素，您可以轻松安全地删除最后一个元素（= 列表的尾元素）。只需迭代到最后一个元素之前的元素，删除最后一个并更新next新的最后一个元素中的指针。请注意，在这种情况下，调用者的head指针将仍然是指向有效列表的完全有效的指针。

However, if the list initially contained only one element (meaning that headis already pointing to the last element) then, of course, you can still easily delete it, but unfortunately you can't update caller's headpointer from inside deletefunction. After such deletion the caller's headpointer will become invalid. It will point to now-deallocated memory, i.e. it will become a dangling pointer.

但是，如果列表最初只包含一个元素（意味着它head已经指向最后一个元素），那么当然，您仍然可以轻松删除它，但不幸的是，您无法head从delete函数内部更新调用者的指针。在这样的删除之后，调用者的head指针将变得无效。它将指向现在释放的内存，即它会变成一个悬空指针。

Typically, when one implements a function like that, one should make sure that the caller will know when the list becomes empty. It can be implemented in different ways. For example, the caller's headpointer can be made accessible and modifiable from inside the deletefunction if the first parameter is declared as a pointer-to-pointer to head node

通常，当实现这样的函数时，应该确保调用者知道列表何时变空。它可以以不同的方式实施。例如，如果第一个参数被声明为指向头节点的head指针，则可以从delete函数内部访问和修改调用者的指针

int delete(struct node **phead, int item)
...
delete(&head, 42);

Alternatively deletefunction can be made to always return the updated head pointer value

或者，delete可以使函数始终返回更新的头指针值

struct node *delete(struct node *head, int item);
...
head = delete(head, 42);

I don't know whether that issue point is important in your case. The fact that you mention that head"is not pointer-to-pointer" suggests that this might indeed be important.

我不知道这个问题点对你的情况是否重要。您提到head“不是指针到指针”这一事实表明这可能确实很重要。

P.S. I suspect that the word "last" in your question does not refer to the tail element of the list, but rather refers to the last remaining element of the list. I.e. the question is specifically about the situation when there's only one element left. In that case, see above...

PS我怀疑您的问题中的“last”一词不是指列表的尾部元素，而是指列表的最后一个剩余元素。即问题是关于只剩下一个元素的情况。在这种情况下，请参见上文...

回答by Kartik Gogia

This code will work for deleting the last element of a linked list.

此代码将用于删除链表的最后一个元素。

void dellast()
{

r=head;

    struct node* z;
    do
    {
        z=r;
        r=r->next;
        if(r->next==NULL)
        {
            z->next=NULL;
            free(r->next);
        }   
    }while(z->next!=NULL);
}

回答by BOSCO

Yes it's easy.. Proceed as according.. Suppose your linked list has first node header last node 'last'..then adding any node temp and ctemp...

是的，这很容易.. 继续按照.. 假设你的链表有第一个节点头最后一个节点'last'..然后添加任何节点 temp 和 ctemp ...

temp = header;
while(temp->link != NULL)
{
    ctemp = temp;
    temp = temp->link;
}
ctemp->link = NULL;
delete temp;

回答by Gewure

I've done the same as you and struggled at the same point, but finally implemented it cleanly. Feel free to use the code. Your problem is handled in int remove_end(LinkedList *list).

我和你做了同样的事情并且在同一点上挣扎，但最终干净利落地实现了它。随意使用代码。您的问题在int remove_end(LinkedList *list).

Here the full working implementation:

这里是完整的工作实现：

#include  <stdio.h>
#include <stdlib.h>
#include <string.h>

/********** GLOBALS *******************************/
#define OK 0
#define ERROR -1

/********** STRUCT AND TYPES DEFINTIONS ***********/
/* a node with key, data and reference to next node*/
typedef struct Node {
    int key;
    char string[1024];
    struct Node *next;  // pointer to next node
} Node;

/* the actual linked list: ref to first and last Node, size attribute */
typedef struct LinkedList {
    struct Node *first;
    struct Node *last;
    int size;
} LinkedList;

/********** FUNCTION HEADERS **********************/
LinkedList* init_list();
void insert_end(LinkedList *list, int key, char string[]);
void insert_beginning(LinkedList *list, int key, char string[]);
int remove_end(LinkedList *list);
int remove_beginning(LinkedList *list);
int print_list(LinkedList *list);
void free_list(LinkedList *list);
char * get_string(LinkedList *list, int key);

/*********** FUNCTION DEFINITIONS ***************/

/**
 * init_list Returns an appropriately (for an empty list) initialized struct List
 *
 * @return LinkedList *         ..ptr to the newly initialized list
 */
LinkedList * init_list() {
    printf("initializing list...\n");

    LinkedList *list = (LinkedList*) malloc(sizeof(LinkedList));

    list->first = NULL;
    list->last = NULL;
    list->size = 0;

    return list;
}

/**
 * Given a List, a key and a string adds a Node containing this
 * information at the end of the list
 *
 * @param list      LinkedList *    ..ptr to LinkedList
 * @param key       int             .. key of the Node to be inserted
 * @param string    char[]          .. the string of the Node to be inserted
 */
void insert_end(LinkedList *list, int key, char string[]) {
    printf("----------------------\n");

    list->size++;                    // increment size of list

    // intialize the new Node
    Node* newN = (Node*) malloc(sizeof(Node));
    newN->key = key;
    strcpy(newN->string, string);
    newN->next = NULL;

    Node* oldLast = list->last;      // get the old last
    oldLast->next = newN;          // make new Node the next Node for oldlast
    list->last = newN;              // set the new last  in the list

    printf("new Node(%p) at end: %d '%s' %p \n", newN, newN->key, newN->string,newN->next);
}

/**
 * Given a List, a key and a string adds a Node, containing
 * this information at the beginning of the list
 *
 * @param list      LinkedList *    ..ptr to LinkedList
 * @param key       int             .. key of the Node to be inserted
 * @param string    char[]          .. the string of the Node to be inserted
 */
void insert_beginning(LinkedList *list, int key, char string[]) {
    printf("----------------------\n");

    list->size++;                    // increment size of list
    Node* oldFirst = list->first;    //get the old first node

    /* intialize the new Node */
    Node* newN = (Node*) malloc(sizeof(Node));
    newN->key = key;
    strcpy(newN->string, string);
    newN->next = oldFirst;

    list->first = newN;              // set the new first

    /* special case: if list size == 1, then this new one is also the last one */
    if (list->size == 1)
        list->last = newN;

    printf("new Node(%p) at beginning: %d '%s' %p \n", newN, newN->key,newN->string, newN->next);
}

/**
 * Removes the first Node from the list
 *
 * @param list      LinkedList *        .. ptr to the List
 *
 * @return OK | ERROR
 */
int remove_beginning(LinkedList *list) {
    printf("----------------------\n");

    if (list->size <= 0)
        return ERROR;

    list->size--;

    Node * oldFirst = list->first;

    printf("delete Node(%p) at beginning: '%d' '%s' '%p' \n", oldFirst,oldFirst->key, oldFirst->string, oldFirst->next);

    free(list->first);          //free it
    list->first = oldFirst->next;
    oldFirst = NULL;

    return OK;
}

/**
 * Removes the last Node from the list.
 *
 * @param list      LinkedList *        .. ptr to the List
 *
 * @return OK | ERROR
 */
int remove_end(LinkedList *list) {
    printf("----------------------\n");

    /* special case #1 */
    if (list->size <= 0)
        return ERROR;

    /* special case #2 */
    if (list->size == 1) {
        free(list->first);
        list->first = NULL;
        list->last = NULL;
        return OK;
    }

    printf("delete Node(%p) at end: '%d' '%s' '%p' \n", list->last,list->last->key, list->last->string, list->last->next);

    list->size--;           // decrement list size
    Node * startNode = list->first;

    /* find the new last node (the one before the old last one); list->size >= 2 at this point!*/
    Node * newLast = startNode;
    while (newLast->next->next != NULL) {
        newLast = newLast->next;
    }

    free(newLast->next);    //free it
    newLast->next = NULL;   //set to NULL to denote new end of list
    list->last = newLast;   // set the new list->last

    return OK;
}

/**
 * Given a List prints all key/string pairs contained in the list to
 * the screen
 *
 * @param list      LinkedList *        .. ptr to the List
 *
 * @return  OK | ERROR
 */
int print_list(LinkedList *list) {

    printf("----------------------\n");

    if (list->size <= 0)
        return ERROR;

    printf("List.size = %d \n", list->size);

    Node *startN = list->first;  //get first

    /* iterate through list and print contents */
    do {
        printf("Node#%d.string = '%s', .next = '%p' \n", startN->key,startN->string, startN->next);
        startN = startN->next;
    } while (startN != NULL);

    return OK;
}

/**
 * Given a List, frees all memory associated with this list.
 *
 * @param list      LinkedList *        ..ptr to the list
 */
void free_list(LinkedList *list) {
    printf("----------------------\n");
    printf("freeing list...\n");

    if (list != NULL && list->size > 0) {
        Node * startN = list->first;
        Node * temp = list->first;

        do {
            free(temp);
            startN = startN->next;
            temp = startN;
        } while (startN != NULL);

        free(list);
    }
}

/**
 * Given a List and a key, iterates through the whole List and returns
 * the string of the first node which contains the key
 *
 * @param list      LinkedList *        ..ptr to the list
 * @param key       int                 .. the key of the Node to get the String from
 *
 * @return OK | ERROR
 */
char * get_string(LinkedList *list, int key) {
    printf("----------------------\n");

    Node *startN = list->first;  //get first

    /* if only one node.. */
    if(list->size == 1)
        return startN->string;

        /* iterate through list and find Node where node->key == key */
    while (startN->next != NULL) {
        if (startN->key == key)
            return startN->string;
        else
            startN = startN->next;
    }

    return NULL;
}

/*************** MAIN **************/
int main(void) {

    LinkedList *list = init_list();

    insert_beginning(list, 1, "im the first");
    insert_end(list, 2, "im the second");
    insert_end(list, 3, "im the third");
    insert_end(list, 4, "forth here");

    print_list(list);
    remove_end(list);
    print_list(list);
    remove_beginning(list);
    print_list(list);
    remove_end(list);
    print_list(list);
    printf("string at node with key %d = '%s' \n",2,get_string(list, 2));
    free_list(list);

    return OK;
}

TRY IT ONLINE

在线试用

回答by Deep

Deleting a node from any position of the linked list can done by the code given below.

可以通过下面给出的代码从链表的任何位置删除节点。

void DeleteNodeFromLinkedList(struct ListNode* head,int position){
 int k=1;
 struct ListNode *p,*q;
 if(*head==NULL){
     printf("List Empty");
     return;
 }
 if(postion==1){
     *head=(*head)->next;
      free(p);
      return ;
 }
 else{
   while(p!=NULL&&k<position)
       {
          k++;
          q=p;
          p=p->next;
        }
   if(p==NULL)
       {
          printf("Position of the node doesnt exist");
          return ;
          }
   else
       {
           q->next=P->next;
           free(p);
           return ;
       }
   }
  }

Time Complexity:O(n) Space Complexity:O(1)

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

回答by Novicegama666

void delete_last(){    
    struct node *ptr=start;
    while(ptr->next->next!=NULL){
        ptr=ptr->next;
    }
    ptr->next=NULL;
    free(ptr->next);    
}

回答by dchayes12

Yes, you can just cycling through each list_node->next, starting with head->next until list_node->next is null. At that point the current list_node is the one to be deleted. If I understand your question correctly...

是的，您可以循环遍历每个 list_node->next，从 head->next 开始，直到 list_node->next 为空。在这一点上，当前的 list_node 是要删除的。如果我正确理解您的问题...

回答by Ayse

If you're looking for a way to delete the last node of the linked list, this code will work for you :)

如果您正在寻找一种删除链表最后一个节点的方法，此代码对您有用:)

int delete(struct node *head, int item)
    {
        if(head==NULL)
        {
            printf("\n\t\t~~~NO NODE PRESENT~~~\n\t\t\t :p\n");
            return 0;
        }
        else
        {
            struct node*temp;
            struct node*temp2;
            temp=head; // just to keep a record of original head.
            while(temp->n->n !=NULL)
            {
                temp=temp->n;
            }
            temp2=temp->n;
            temp->n=NULL;
            free(temp2);
        }
        return 0;
    }