Блог

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

ДА.

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

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

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

}
  

DeleteLastOccurenceOfKey(head,25);

Ввод / вывод: 5 10 15 25 35 25 40 Вывод / вывод: 5 10 15 25 35 40

 /*
 * 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 emptyn");
        return;
    }

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

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

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

    if (prev){
        prev->next = match->next;
        printf ("Delete %dn", 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 %dn", cur->d);
            free (cur);
        } else {
            printf ("No matchn");
        }
    }

    printL(*head);
}




int main (int argc , char *argv) {

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

 public void deleteLastOccurence(int value) {
        Element cur = this.head;
        Element prev = null;
        Element tmp = null;
        
        if(this.head == null)
            return;
        
        if(this.head.data == value) {
            this.head = null;
            return;
        }
        
        while(cur != null) {
            if(cur.next != null amp;amp; cur.next.data == value) {
                prev = cur;
                tmp = cur.next;
            }
            cur = cur.next;
        }
        prev.next = tmp.next;
    }