如何对链表进行排序？

Question

我有一个链接列表，我想按特殊顺序对其进行排序。我尝试使用冒泡排序。由于我的struct（称为Node）中有许多数据类型，因此无法交换值。

struct Node
{
    int data;
    Node *next;

    Node(int x)
    {
        data = x;
        next = NULL;
    }

    union
    {
        sold s;
        apartment a;
        villa v;

    }u;

};

实际上，我无法在my_swap函数中交换联合值。我需要的是一个新的交换功能。这是我的代码。

#include<iostream>
#include<vector>
#include<string>

using namespace std;

struct adderess {
    char city[50];
    char street[100];
    char alley[100];
    int code;
};

struct apartment {

    float structure_s;
    float price;
    int floor;
    bool elevator;
    adderess adr;

};
struct villa {
    float structure_s;
    float yard_s;
    float price;
    int floor;
    adderess adr;
};

struct sold {
    int type;
    float comission;
    bool con;

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

    Node(int x)
    {
        data = x;
        next = NULL;
    }

    union
    {
        sold s;
        apartment a;
        villa v;

    }u;

};


void print_list(Node *head)
{
    Node *start = head;

    while (start)
    {
        cout << start->data << " -> ";
        start = start->next;
    }
    cout << "\n\n";
}

void my_swap(Node *node_1, Node *node_2)
{
    int temp = node_1->data;
    node_1->data = node_2->data;
    node_2->data = temp;
}
double total_price(Node **n) {
    if ((*n)->data == 1)
        return((*n)->data*(*n)->data);

    else 
        return((*n)->data*(*n)->data*(*n)->data);

}
void bubble_sort(Node *head)
{
    int swapped;

    Node *lPtr; // left pointer will always point to the start of the list
    Node *rPrt = NULL; // right pointer will always point to the end of the list
    do
    {
        swapped = 0;
        lPtr = head;
        while (lPtr->next != rPrt)
        {
            if (total_price(&lPtr) >total_price(& lPtr->next))
            {
                my_swap(lPtr, lPtr->next);
                swapped = 1;
            }
            lPtr = lPtr->next;
        }
        //as the largest element is at the end of the list, assign that to rPtr as there is no need to
        //check already sorted list
        rPrt = lPtr;

    } while (swapped);
}

int main()
{
    Node *head = new Node(2);
    head->next = new Node(1);
    head->next->next = new Node(4);
    head->next->next->next = new Node(3);
    head->next->next->next->next = new Node(6);
    head->next->next->next->next->next = new Node(5);

    cout << "The original list = " << endl;
    print_list(head);


    bubble_sort(head);

    cout << "The Sorted list = " << endl;
    print_list(head);

    return 0;
}

Answer 1

您可以在链接列表中交换它们的位置，而不是交换两个节点中的值。为此，您需要维护一个prev指针，该指针是链表中lPtr之前的指针。

void my_swap(Node*& head, Node*& prev, Node*& node_1, Node*& node_2)
{
    if (prev == nullptr)
    {
        node_1->next = node_2->next;
        node_2->next = node_1;
        prev = node_2;
        head = node_2;
    }
    else
    {
        node_1->next = node_2->next;
        node_2->next = node_1;
        prev->next = node_2;
        prev = node_2;
    }
}

void bubble_sort(Node *head)
{
    bool swapped;

    Node *prev, *lPtr, *rPtr; // left pointer will always point to the start of the list
    rPtr = nullptr; // right pointer will always point to the end of the list
    do
    {
        swapped = false;
        prev = nullptr;
        lPtr = head;
        while (lPtr->next != rPtr)
        {
            if (total_price(&lPtr) > total_price(&lPtr->next))
            {
                my_swap(head, prev, lPtr, lPtr->next);
                swapped = true;
            }
            else
                lPtr = lPtr->next;
        }
        //as the largest element is at the end of the list, assign that to rPtr as there is no need to
        //check already sorted list
        rPtr = lPtr;

    } while (swapped);
}

我还没有检查它是否可以正常运行，但是希望您在阅读完代码后就明白了。