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

Question

В списке удаляется предидущий элемент перед КАЖДЫМ отрицательным элементом, как сделать, чтобы удалялся после КАЖДОГО следующего?

    class Program
    {
        public struct MyList  
        {
            public double Data; 
            public unsafe MyList* Next; 
        }

        static unsafe void Main(string[] args)
        {
            // указатель на первый элемент списка
            MyList* Head = null;
            // указатель на последний элемент списка (по необходимости)
            MyList* Last = null;
            //Введення першого елемента списку
            Console.WriteLine("Признак конца последоватольности- 0.\nВведите елемент: ");
            int n = int.Parse(Console.ReadLine());
            int count = 0;   // Счетчик элементов списка
            while (n != 0) 
            {
                //Створюємо елемент списку
                MyList* Current = stackalloc MyList[sizeof(MyList)];
                Current->Data = n; 
                Current->Next = null; 

                if (Head == null)  
                {                  
                    Head = Last = Current;
                }
                else
                {
                    Last->Next = Current;
                    Last = Current;
                }                
                Console.WriteLine("Признак конца последоватольности- 0.\nВведите елемент: ");
                n = int.Parse(Console.ReadLine());
                count++;
            }
            Console.WriteLine("Количество элементов в списке: {0}", count);
            MyList* Cur = Head;
            MyList* Curr = Head;
            Curr = Head;
            MyList* NewItem = stackalloc MyList[sizeof(MyList)];
            NewItem->Data = 33;
            for (int i = 1; i < count && Curr->Next != null; i++)
            {
                Curr = Curr->Next;
            }
            Curr->Next = NewItem;
            Cur = Head;
            while (Cur != null) 
            {
                Console.WriteLine(Cur->Data); 
                Cur = Cur->Next; 
            }
            MyList* Curr1 = Head;

            if (Curr1 != null) 
            {
                if (Curr1->Next->Data < 0)
                    Head = Head->Next;
            }
            Curr1 = Head;
            while (Curr1->Next != null)
            {
                if (Curr1->Next->Data < 0) //если меньше 0, то сдвигает указатели, тем самым удаляет элемент перед ним
                {
                    MyList* ptr = Head;
                    while (ptr->Next != Curr1) ptr = ptr->Next;
                    ptr->Next = Curr1->Next;
                    Curr1 = ptr;
                }
                Curr1 = Curr1->Next;
            }

            Cur = Head;
            while (Cur != null) 
            {
                Console.WriteLine(Cur->Data); // Вывод значения информационного поля
                Cur = Cur->Next; 
            }
            Console.ReadLine();
        }
    }
}

Дополнительно

Пример удаления после первого отрецательного.

  MyList* Curr1 = Head;
            while (Curr1->Data >= 0)
                Curr1 = Curr1->Next;

            if (Curr1->Next != null)
            {
                Curr1->Next = Curr1->Next->Next;
            }

Как сделать, чтобы после каждого отрецательного?

Answer 1

Просто установите следующий элемент в element.Next.Next:

if(node.Next != null)
{
    node.Next = node.Next.Next;
}

(Проверка: если отрицательный элемент - последний элемент списка, то после него ничего удалять не нужно)

Пример:

void Main()
{
    int[] arr = new[] { 4, 0, -5, 7, 2 };
    var list = ConstructLinkedList(arr);
    //list.Dump();
    
    var node = list;
    
    while(node.Data >= 0)
        node = node.Next;
        
    if(node.Next != null)
    {
        node.Next = node.Next.Next;
    }
    
    //list.Dump();
}

До удаления элемента:

После удаления элемента:

PS Дополнительный код для запуска примера:

// Define other methods and classes here

#region unit-tests helpers

public class MyList
{
    public MyList(int data)
    {
        this.Data = data;
    }
    public int Data;
    public MyList Next;
}

private MyList ConstructLinkedList(int[] values)
{
    MyList head = null;
    MyList tail = null;

    for (int i = 0; i < values.Length; i++)
    {
        MyList current = new MyList(values[i]);
        if (head == null)
        {
            head = current;
            tail = current;
        }
        else
        {
            tail.Next = current;
            tail = current;
        }
    }

    return head;
}

private int[] ToArray(MyList head)
{
    var result = new List<int>();
    var tmp = head;
    while (tmp != null)
    {
        result.Add(tmp.Data);
        tmp = tmp.Next;
    }
    return result.ToArray();
}

#endregion

Answer 2

Несмотря на то, что при аллокациях в стеке использовать ООП проблематично, так как куча не используется, и объектов как таковых нет, все равно надо стараться разбивать код на методы, иначе получится очень длинный и совсем непонятный код.

Я написал несколько примеров реализации методов работы с таким списком на базе указателей.

public unsafe struct ListNode  
{
    public int Value; 
    public ListNode* Next; 
}

public unsafe struct SingleLinkedList
{
    public ListNode* Head;
    public ListNode* Tail;
    public int Count;

    public static void AddLast(SingleLinkedList* list, ListNode* node)
    {
        if (list->Tail != null)
            list->Tail->Next = node;
        else
            list->Head = node;
        list->Tail = node;
        list->Count++;
    }

    public static void AddFirst(SingleLinkedList* list, ListNode* node)
    {
        if (list->Head != null)
            node->Next = list->Head;
        else
            list->Tail = node;
        list->Head = node;
        list->Count++;
    }

    public static void InsertAfter(SingleLinkedList* list, ListNode* node, ListNode* newNode)
    {
        if (node == list->Tail)
            AddLast(list, newNode);
        else
        {
            if (node->Next != null)
                newNode->Next = node->Next;
            node->Next = newNode;
        }
    }
}

Проверяем

#pragma warning disable CA2014 // Do not use stackalloc in loops
static unsafe void Main(string[] args)
{
    Console.WriteLine("Признак конца последоватольности - 0");
            
    SingleLinkedList* list = stackalloc SingleLinkedList[sizeof(SingleLinkedList)];

    int n;
    while(true)
    {
        Console.Write("Введите элемент: ");
        n = int.Parse(Console.ReadLine());
        if (n == 0)
            break;
        ListNode* node = stackalloc ListNode[sizeof(ListNode)];
        node->Value = n;
        SingleLinkedList.AddLast(list, node);
    }

    Console.WriteLine($"Введено элементов: {list->Count}");
    PrintList(list);

    Console.WriteLine("Проверка добавления элементов:");
    // добавить в конец
    ListNode* newNode = stackalloc ListNode[sizeof(ListNode)];
    newNode->Value = 33;
    SingleLinkedList.AddLast(list, newNode);
    // добавить в начало
    ListNode* newNode2 = stackalloc ListNode[sizeof(ListNode)];
    newNode2->Value = 44;
    SingleLinkedList.AddFirst(list, newNode2);
    PrintList(list);

    Console.ReadKey();
}
#pragma warning restore CA2014 // Do not use stackalloc in loops

private static unsafe void PrintList(SingleLinkedList* list)
{
    Console.WriteLine("Список элементов:");
    if (list == null || list->Head == null)
        return;
    ListNode* node = list->Head;
    while (node != null)
    {
        Console.WriteLine(node->Value);
        node = node->Next;
    }
}

Вывод в консоль

Признак конца последоватольности - 0
Введите элемент: 2
Введите элемент: 3
Введите элемент: 4
Введите элемент: 0
Введено элементов: 3
Список элементов:
2
3
4
Проверка добавления элементов:
Список элементов:
44
2
3
4
33

Удалить элемент после первого отрицательного

ListNode* neg = list->Head;
while (neg != null && neg->Value >= 0)
    neg = neg->Next;
if (neg != null && neg->Next != null)
    neg->Next = neg->Next->Next;

После каждого отрицательного

ListNode* neg = list->Head;
while (neg != null)
{
    while (neg != null && neg->Value >= 0)
        neg = neg->Next;
    if (neg != null && neg->Next != null)
    {
        neg->Next = neg->Next->Next;
        list->Count--;
        neg = neg->Next;
    }
}

Но здесь есть нюанс: если после отрицательного идет еще одно отрицательное, то после второго отрицательного подряд следующая нода удалена не будет. Не знаю, подходит такое решение вам или нет.

А нормальное решение можно реализовать с помощью вот такого рекурсивного метода

private static unsafe void RemoveAllAfterNegative(SingleLinkedList* list, ListNode* startNode)
{
    ListNode* node = startNode;
    while (node != null)
    {
        while (node != null && node->Value >= 0)
            node = node->Next;
        if (node != null && node->Next != null)
        {
            if (node->Next->Value < 0)
                RemoveAllAfterNegative(list, node->Next);
            node->Next = node->Next->Next;
            node = node->Next;
        }
    }
}

И вот так его вызвать

RemoveAllAfterNegative(list, list->Head);

Но вообще после этого вопроса я еще больше полюбил ООП.

БЛОГ НА HUSL

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

Ответы (2 шт):