Удалить последние два элемента из связанного списка в C

Question

У меня есть этот фрагмент кода, он удаляет последний элемент из связанного списка. Какие изменения я должен сделать, чтобы удалить последние два элемента связанного списка?

void deletesEnd() { 
    struct node *temp, *last; 

    temp = head; 
    last = temp; 

    while (temp != NULL && temp->next != NULL) { 
     last = temp; 
     temp = temp->next; 
    } 

    if (last == temp) { 
     free(temp); 
     head = NULL; 
    } else { 
     free(last->next); 
     last->next = NULL; 
    } 
} 

Answer 1

Вот демонстративная программа, которая показывает, как два последних узла могут быть удалены одновременно. Фактически функция похожа на вашу функцию, за исключением проверки не только узла next, но и узла next->next.

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

struct node 
{ 
    int value; 
    struct node *next; 
} *head; 

void push(int value) 
{ 
    struct node *tmp = malloc(sizeof(struct node)); 
    tmp->value = value; 
    tmp->next = head; 

    head = tmp; 
} 

void display() 
{ 
    for (struct node *current = head; current; current = current->next) 
    { 
     printf("%d ", current->value); 
    } 
} 

void deleteLastTwo() 
{ 
    struct node *current = head; 
    struct node *prev = head; 

    if (current && current->next) 
    { 
     while (current->next->next) 
     { 
      prev = current; 
      current = current->next; 
     } 
    } 

    if (current) 
    { 
     if (current->next) 
     { 
      free(current->next); 
     } 

     if (prev == current) 
     { 
      head = NULL; 
     } 
     else 
     { 
      prev->next = NULL; 
     } 

     free(current); 
    } 
} 

int main(void) 
{ 
    const int N = 11; 

    for (int i = N; i != 0; i--) push(i - 1); 

    display(); 
    printf("\n"); 

    while (head) 
    { 
     deleteLastTwo(); 
     display(); 
     printf("\n"); 
    } 

    return 0; 
} 

Выход программы

0 1 2 3 4 5 6 7 8 9 10 
0 1 2 3 4 5 6 7 8 
0 1 2 3 4 5 6 
0 1 2 3 4 
0 1 2 
0 

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

Answer 2

Эта логика удалит ваш последний 2 узла в одиночном списке.

void deletesEnd() 
{ 
    struct node *temp, *last; 

    temp = head; 
    last = temp; 

    while (temp->next->next != NULL) 
    { 
     last = temp->next; 
     if(last->next->next!=NULL) 
       temp = temp->next; 
     else 
       break; 
    } 

     struct node *ptr=last->next; 
     last->next=ptr->next; 
     free(ptr); 

     temp->next=last->next; 
     free(last); 
} 

Answer 3

Для развлечения & образование: простая рекурсивная версия.

• Функция возврата: = число узлов нижеus
• После возвращения рекурсии, мы можем решить, если мы слишком близко к хвосту.
• и удалить себя
• , потому что мы передаем указатель на указатель, это также должно работать для списков размера = 2 и меньше

---

unsigned del_tail_n(struct llist **pp, unsigned nn) 
{ 
unsigned pos; 
if (!*pp) return 0; 

    // this recursive call returns 0 iff (*pp)->next is NULL 
pos = del_tail_n(&(*pp)->next, nn); 
if (pos < nn) { 
     // free (*pp); 
     *pp = NULL; 
     } 
return 1+pos; 
} 

---

Для тех, кто не как рекурсия, вот нерекурсивная версия. [не отметить, что обе версии работают для пустых списков (*pp == NULL), или для списков меньше, чем nn]

void del_tail_n2(struct llist **pp, unsigned nn) 
{ 
struct llist *p; 

     /* Advance p pointer n positions down, starting from *pp. */ 
for (p= *pp; p; p=p->next) { 
     if (nn-- < 1) break; 
     } 

     /* Do a synchronous walk down for both p and *pp, until p is NULL. */ 
for (; p; p=p->next) { 
     pp = &(*pp)->next; 
     } 

     /* Now, *pp is the first node to delete 
     ** Delete it and everything below it. 
     */ 
for (;(p = *pp);){ 
     *pp = p->next; 
     // free (p); 
     } 
return; 
} 

Answer 4

Самое простое решение, чтобы удалить последние 2 элемента из списка, чтобы позвонить deletesEnd() дважды. Обратите внимание, что deletesEnd() должен принимать head в качестве аргумента и возвращать новое значение. Вы хотите удалить последние 2 путем выдачи вложенного вызова:

struct node *deletesEnd(struct node *head) { 
    struct node *temp, *last; 

    last = temp = head; 
    while (temp && temp->next != NULL) { 
     last = temp; 
     temp = temp->next; 
    } 
    if (last == head) { 
     free(head); 
     head = NULL; 
    } else { 
     free(last->next); 
     last->next = NULL; 
    } 
    return head; 
} 

Удаление последнего элемента: head = deletesEnd(head);

Удалить последние 2 элемента: head = deletesEnd(deletesEnd(head));

Простота конструкции более чем компенсирует накладные расходы, перечисляющие список дважды.

Если вы хотите абсолютно определенную функцию, вы можете расширить ваш подход таким образом:

struct node *deleteLast2Nodes(struct node *head) { 
    struct node *temp, *last; 

    last = temp = head; 
    while (temp && temp->next != NULL && temp->next->next != NULL) { 
     last = temp; 
     temp = temp->next; 
    } 
    if (last == head) { 
     if (head) { 
      free(head->next); 
     } 
     free(head); 
     head = NULL; 
    } else { 
     free(last->next->next); 
     free(last->next); 
     last->next = NULL; 
    } 
    return head; 
}