我可以使用 C 中的以下原型删除最后一个节点吗 -: int delete(struct node *head, int item)
注意-：这里的第一个参数是指向开始节点的点，而不是指向开始节点的指针。
谢谢
问问题
66195 次
9 回答
9
是的。可以删除单链表的最后一个节点，从第一个节点开始。
试试下面的代码，
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;
}
但是，如果您的链表中只有一个元素，那么在删除该元素后，您的头指针仍将指向您调用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;
}
调用函数delete()如下，
head=delete(head);
于 2013-06-19T06:52:27.057 回答
2
答案取决于问题的确切含义。
当然，如果列表包含多个元素，您可以轻松安全地删除最后一个元素（= 列表的尾部元素）。只需迭代到最后一个元素之前的元素，删除最后一个并更新next新最后一个元素中的指针。请注意，在这种情况下，调用者的head指针将仍然是指向有效列表的完全有效的指针。
但是，如果列表最初只包含一个元素（意味着head已经指向最后一个元素），那么当然，您仍然可以轻松删除它，但不幸的是，您无法从内部函数更新调用者的head指针。delete在这样的删除之后，调用者的head指针将变得无效。它将指向现在释放的内存，即它将成为一个悬空指针。
通常，当实现这样的功能时，应该确保调用者知道列表何时变为空。它可以以不同的方式实现。例如，如果第一个参数声明为指向头节点的指针，head则可以从函数内部访问和修改调用者的指针delete
int delete(struct node **phead, int item)
...
delete(&head, 42);
或者delete可以使函数始终返回更新的头指针值
struct node *delete(struct node *head, int item);
...
head = delete(head, 42);
我不知道这个问题点对你的情况是否重要。您提到head“不是指针对指针”的事实表明这可能确实很重要。
PS我怀疑您问题中的“最后一个”一词不是指列表的尾部元素，而是指列表中最后一个剩余的元素。即，问题具体是关于只剩下一个元素的情况。在这种情况下，请参见上文...
于 2013-06-19T06:56:37.180 回答
0
如果您正在寻找一种方法来删除链表的最后一个节点，此代码将为您工作:)
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;
}
于 2013-06-19T06:53:54.870 回答
0
是的，您可以循环遍历每个 list_node->next，从 head->next 开始，直到 list_node->next 为空。此时，当前的 list_node 是要删除的。如果我正确理解你的问题...
于 2013-06-19T06:51:47.277 回答
0
是的，这很容易..按照..假设您的链表有第一个节点标题最后一个节点“最后一个”..然后添加任何节点 temp 和 ctemp...
temp = header;
while(temp->link != NULL)
{
ctemp = temp;
temp = temp->link;
}
ctemp->link = NULL;
delete temp;
于 2017-02-11T07:02:39.333 回答
0
我和你做的一样，在同一点上挣扎，但最终干净利落地实现了。随意使用代码。您的问题已在int remove_end(LinkedList *list).
这里是完整的工作实现：
#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;
}
于 2017-05-24T10:05:07.700 回答
0
从链表的任何位置删除一个节点可以通过下面给出的代码来完成。
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 ;
}
}
}
时间复杂度：O(n) 空间复杂度：O(1)
于 2017-08-02T08:22:34.287 回答
0
此代码将用于删除链表的最后一个元素。
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);
}
于 2016-07-30T18:40:45.483 回答
0
void delete_last(){
struct node *ptr=start;
while(ptr->next->next!=NULL){
ptr=ptr->next;
}
ptr->next=NULL;
free(ptr->next);
}
于 2017-09-05T04:13:58.517 回答