Как можно разделить односвязный список вокруг значения, используя две отдельные функции в main () - одну lesserThan, а другую greatThan - в C / C ++

Question

У меня есть следующий связанный список: 2-> 1-> 9-> 8-> 3-> 1-> nullptr.

Я хочу разбить связанный список вокруг значения 4 так, чтобы все значения меньше 4, перед всеми значениями больше или равно 4.

Я могу разбить связанный список, используя одну функцию. Но я хочу сделать это, используя две функции - функцию lesserThan(head,x) и функцию greaterThan(head, x) - где x - это значение, вокруг которого я хочу разделить список.

Но я сталкиваюсь со следующей проблемой: если я использую обе функции вместе, узлы списка изменяются первой функцией - и вторая функция работает на этих измененных узлах. Функции работают нормально, когда другая закомментирована. То есть lesserThan(head,x) работает нормально, когда greaterThan(head, x) закомментирован, и наоборот.

Как я могу разбить связанный список, по-прежнему используя обе функции в main ()? Основная проблема, с которой я сталкиваюсь, заключается в том, что узлы модифицируются как в функциях lesserThan, так и в функции lessThan, и это отражается в main ().

Ниже приведен код:

struct Node
{
    int data;
    Node* next;
};

Node* newNode(int data)
{
    Node* temp = new Node;
    temp->data = data;
    temp->next = nullptr;
    return temp;
}

Node* lesserThan(Node* head, int x)
{
    if (head == nullptr)
    {
        return nullptr;
    }

    Node* list1=nullptr, *temp1 = nullptr;

    if ((head)->data < x)
    {
        temp1=list1 = head;
    }
    else
    {
        while (head && head->data >= x)
        {
            head = head->next;
        }
        if (head && head->data < x)
        {
            temp1 = list1 = head;
        }
    }

    Node* curr = temp1;
    if(curr) 
        curr = curr->next;
    while (curr)
    {
        Node* next = curr->next;
        if (curr->data<x)
        {
            list1->next = curr;
            list1 = curr;
            list1->next = nullptr;
        }
        curr = next;
    }
    return temp1;
}

Node* greaterThan(Node* head, int x)
{
    Node* temp2 = nullptr, *list2=nullptr;

    if (head->data >= x)
    {
        temp2 =list2= head;
    }
    else
    {
        while (head && head->data < x)
        {
            head = head->next;
        }
        if (head && head->data >= x)
        {
            temp2 = list2 = head;
        }
    }

    Node* curr = list2;
    if (curr)
        curr = curr->next;
    while (curr)
    {
        Node* next = curr->next;
        if (curr->data >= x)
        {
            list2->next = curr;
            list2 = curr;
            list2->next = nullptr;
        }
        curr = next;
    }
    return temp2;
}

int main()
{
    Node* head = newNode(2);
    head->next = newNode(1);
    head->next->next = newNode(9);
    head->next->next->next = newNode(8);
    head->next->next->next->next = newNode(3);
    head->next->next->next->next->next = newNode(1);
    int x = 4;

    Node* p1 = lesserThan(head,x);
    Node* p2 = greaterThan(head, x);
    if (p1 != nullptr)
        p1->next = p2;

    while (p1)
    {
        cout << p1->data << " ";
        p1 = p1->next;
    }
    cout << endl;
    return 0;
}

Ниже приведены две функции, которые не могут работать вместе, поскольку узлы списка модифицируются первой функцией (и второй функцией), и это отражено в main () -

Как сделать так, чтобы две функции были основными, чтобы они не влияли друг на друга? Я попытался создать разные переменные для головы и передать их функциям. Но это не сработало. Спасибо за помощь!

Answer 1

Будет лучше использовать рекурсивную функцию вставки вместо вашего стиля и учтите, что у вас есть выделенные узлы, которые не были восстановлены. Я не учел их. В любом случае, я думаю, что следующий код работает по назначению

struct Node
{
    Node() = default;
    Node( int dataVal ):data{dataVal}{}
    int data{};
    Node* next{};
};

Node*& lessThan( Node* const & head, int x){

        if( !head ) throw std::invalid_argument("Empty linked list");

        Node* toBeReturned;
        Node*  currentHeadNode = head;
        Node**  currentReturned = & toBeReturned;

        while( currentHeadNode ){

            if(currentHeadNode -> data < x ){

                *currentReturned = new Node{ currentHeadNode -> data };
                currentReturned = &((*currentReturned) -> next);
            }

            currentHeadNode = currentHeadNode->next;
        }

        return toBeReturned;
}

int main()
{
    Node* head = new Node(2);
    head->next = new Node(1);
    head->next->next = new Node(9);
    head->next->next->next = new Node(8);
    head->next->next->next->next = new Node(3);
    head->next->next->next->next->next = new Node(1);
    int x = 4;

    Node* p1 = lessThan(head,x);

    while (p1)
    {
        std::cout << p1->data << " ";
        p1 = p1->next;
    }
    std::cout << std::endl;
    return 0;
}