Поиск и удаление последнего вхождения элемента в (однократно) связанном списке только с одним обходом

Question

Можно ли найти последнее вхождение элемента (например, целое число) и удалить этот узел только одним (прямым) обходом по списку?

Answer 1

Да.

Просто запоминайте предыдущую запись каждый раз, когда вы находите искомое значение в обходе. По завершении обхода последняя запомненная запись будет иметь ссылку на удаляемую запись, и этого достаточно для удаления.

Answer 2

public void DeleteLastOccurenceOfKey(Node head, int key) 
{
    Node current=head;
    Node prev=null;
    Node temp=null;

    while(current!=null)
    {
        if(current.next!=null && current.next.data==key)
        {
        prev=current;
        temp=current.next;
        }
        current=current.next;
    }
    prev.next=temp.next;

}

DeleteLastOccurenceOfKey (голова, 25);

I / P: 5 10 15 25 35 25 40 O / P: 5 10 15 25 35 40

Answer 3

/*
 * Delete last occurrence of an item from linked list
 * Given a liked list and a key to be deleted. Delete last occurrence of key
 * from linked. The list may have duplicates.
 *
 * Examples:
 *
 * Input:   1->2->3->5->2->10, key = 2`enter code here`
 * Output:  1->2->3->5->10
 */


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

typedef struct list_ list;
struct list_ {
    int d;
    list *next;
};


void insert (list **head, int d) {
    list *tmp = (list *)malloc(sizeof(list));
    assert(tmp);
    tmp->d = d;
    tmp->next = *head;
    *head = tmp;
}

void printL (list *p) {
    while (p) {
        printf (" %d ", p->d);
        p = p->next;
    }
    printf ("\n");
}


void deletlastOccurence (list **head, int d) {

    list *cur = *head;
    list *prev = NULL;
    list *match = NULL;

    if (cur == NULL) {
        printf ("list is empty\n");
        return;
    }

    /*
     * Special case when there only ONE NODE
     * in the LIST
     */
    if (cur->next == NULL) {
        if (cur->d == d) {
            printf ("Deleted one node %d\n", cur->d);
            free(cur);
            *head = NULL;
        } else {
            printf(" No match\n");
        }
        return;
    }

    /*
     * Keep track of previous node
     */
    while (cur && cur->next) {

        if (cur->next->d == d) {
            prev = cur;
            match = cur->next;
        }
        cur = cur->next;
    }

    if (prev){
        prev->next = match->next;
        printf ("Delete %d\n", match->d);
        free (match);
    } else {
        /*
         * Special case when the last node is
         * on the head itself
         */
            if ((*head)->d == d) {
            cur = *head;
            *head = cur->next;
            printf("element is at head Delete %d\n", cur->d);
            free (cur);
        } else {
            printf ("No match\n");
        }
    }

    printL(*head);
}




int main (int argc , char *argv) {

    list *h = NULL;
    insert(&h, 1);
    insert(&h, 2);
    insert(&h, 3);
    insert(&h, 4);
    insert(&h, 5);
    insert(&h, 2);
    insert(&h, 1);
    insert(&h, 6);
    printL(h);
    deletlastOccurence(&h, 6);
    deletlastOccurence(&h, 2);
}