如何在 main() 中使用两个单独的函数 - 一个 lesserThan 和另一个 greaterThan - 在 C/C++ 中围绕一个值划分单向链表

Question

我有如下链表： 2->1->9->8->3->1->nullptr.

我想围绕值 4 对链表进行分区，这样所有小于 4 的值都排在所有大于或等于 4 的值之前。

我可以使用单个函数对链表进行分区。但是，我想使用两个函数来完成它 - 一个函数 lesserThan(head,x) 和一个函数 greaterThan(head, x) - 其中 x 是我要围绕其对列表进行分区的值。

但是，我运行遇到了以下问题：如果我同时使用这两个函数，列表节点将由第一个函数修改 - 并且第二个函数在修改后的节点上运行。当另一个被注释掉时，这些功能工作正常。也就是说，当 greaterThan(head, x) 被注释掉时，lesserThan(head,x) 工作正常，反之亦然。

如何通过仍然使用 main() 中的两个函数来划分链表？我遇到的主要问题是节点在 lesserThan 和 greaterThan 函数中都被修改了，这反映在 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() -

如何将这两个函数放在main中，使它们互不影响？我尝试为 head 创建不同的变量，并将它们传递给函数。但这没有用。感谢您的帮助！

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;
}

如何在 main() 中使用两个单独的函数 - 一个 lesserThan 和另一个 greaterThan - 在 C/C++ 中围绕一个值划分单向链表

How can I partition a singly linked list around a value, using two seperate functions in main() - one lesserThan and the other greaterThan - in C/C++

c++

singly-linked-list