我可以在C -中使用以下原型删除最后一个节点吗?Int delete(struct node *head, Int item)
注意-:这里的第一个参数是指向开始节点的点，而不是指向开始节点的指针。
谢谢
是。可以删除单链表的最后一个节点，从第一个节点开始。
试试下面的代码
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);
答案取决于问题的确切含义。
当然，如果列表包含多个元素，则可以轻松安全地删除最后一个元素(=列表的尾部元素)。只需迭代到最后一个元素之前的元素，删除最后一个元素并更新新的最后一个元素中的next指针。注意，在这种情况下，调用者的head指针仍然是一个指向有效列表的完全有效的指针。
然而，如果列表最初只包含一个元素(意味着head已经指向最后一个元素)，那么当然，你仍然可以很容易地删除它，但不幸的是，你不能从delete函数内部更新调用方的head指针。删除之后，调用方的head指针将失效。它将指向现在已被释放的内存，也就是说，它将成为一个悬空指针。
通常，当实现这样的函数时，应该确保调用者知道列表何时变为空。它可以以不同的方式实现。例如，如果将第一个参数声明为指向头节点
的指针，则可以从delete函数内部访问和修改调用方的head指针。int delete(struct node **phead, int item)
...
delete(&head, 42);
或者可以使delete函数始终返回更新后的头指针值
struct node *delete(struct node *head, int item);
...
head = delete(head, 42);
head"不是指针对指针"这一事实表明，这可能确实很重要。
注:我怀疑你问题中的"last"一词不是指列表的尾部元素，而是指列表的最后剩余元素。也就是说，这个问题是关于只剩下一个元素的情况。
是的，您可以循环遍历每个list_node->next，从head->next开始，直到list_node->next为空。此时，当前的list_node就是要删除的。如果我对你的问题理解正确的话……
如果您正在寻找一种方法来删除链表的最后一个节点，这段代码将为您工作:)
int delete(struct node *head, int item)
{
if(head==NULL)
{
printf("ntt~~~NO NODE PRESENT~~~nttt :pn");
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;
}
这段代码将用于删除链表的最后一个元素。
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);
}
是的，这很容易。按照…假设你的链表有第一个节点头最后一个节点'最后'..然后添加任何节点temp和ctemp…
temp = header;
while(temp->link != NULL)
{
ctemp = temp;
temp = temp->link;
}
ctemp->link = NULL;
delete temp;
我做过和你一样的事情，在同一点上挣扎，但最终实现了它干净。请随意使用代码。您的问题已在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;
}
上网试试
可以使用下面的代码从链表的任何位置删除一个节点。
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)
void delete_last(){
struct node *ptr=start;
while(ptr->next->next!=NULL){
ptr=ptr->next;
}
ptr->next=NULL;
free(ptr->next);
}