C++ 使用链表对给定字符数组进行排序

在这个问题中，我们需要使用链表对给定的字符数组进行排序。我们可以使用冒泡排序、选择排序、归并排序等技术来对数组进行排序。

在这里，我们首先将数组转换为链表，然后使用选择排序和冒泡排序技术对数组进行排序。

问题描述 −我们已经给出了长度为N的数组arr[]。数组包含小写字母字符。我们需要使用链表对数组进行排序。

示例

输入

arr[] = {'e', 's', 'a', 'x', 'c', 'e','f', 'p', 'b', 'n', 'a'};

输出

a -> a -> b -> c -> e -> e -> f -> n -> p -> s -> x -> NULL

解释 - 我们已经按升序对数组进行了排序。

输入

arr[] = {'g', 'g', 'h', 'i', 'j', 'k', 'k', 'l', 'm', 'n', 'o'};

输出

g -> g -> h -> i -> j -> k -> k -> l -> m -> n -> o -> NULL

解释 − 数组arr[]和输出与数组已经排序相同。

方法1

在这个方法中，我们将使用冒泡排序算法来对链表进行排序。首先，我们将数组转换为链表，然后使用冒泡排序技术。在冒泡排序技术中，我们进行总共N次迭代，交换所有大于下一个元素的链表元素。

步骤

步骤1 − sortLinkedList()函数用于对链表进行排序，它接受起始节点和链表长度作为参数。

步骤2 − 定义“curr”节点和“swapped”布尔变量来跟踪在单个迭代中是否发生了交换。

步骤3 − 使用循环遍历链表。将“start”节点赋值给“curr”，并将“swapped”初始化为false。

步骤4 − 现在，使用另一个嵌套循环进行迭代，直到len − p − 1。分别将“temp1”和“temp2”变量定义为“curr”节点及其下一个节点。

步骤5 − 如果temp1 −> ch大于temp2 −> ch，则交换它们并更新“curr”节点和“swapped”变量的值。

步骤6 − 将“curr”移动到下一个节点。

步骤7 − 如果swapped == false并且在使用嵌套循环进行迭代时没有更新，则中断外部循环，因为列表已经排序。

示例

在这个示例中，我们使用结构体来创建一个链表。同时，我们定义了addNode()函数来将节点插入当前链表。我们使用addNode()函数将数组的每个元素添加为字符到链表中。

addNode()函数遍历链表直到找到最后一个节点，并在最后添加新节点。

#include <iostream>
using namespace std;

// creating the struct listNode
struct listNode {
    int ch;
    listNode *next;
} listNode;

// Swapping the nodes of the linked list
struct listNode *swap(struct listNode *pointer1, struct listNode *pointer2) {
    struct listNode *tmp = pointer2->next;
    pointer2->next = pointer1;
    pointer1->next = tmp;
    return pointer2;
}
// Sorting the linked list
void sortLinkedList(struct listNode **start, int len) {
    // storing the current node
    struct listNode **curr;
    int p, q;
    bool swapped = false;
    for (p = 0; p <= len; p++) {
        // store the current node address in curr
        curr = start;
        swapped = false;
        // traverse the list
        for (q = 0; q < len - p - 1; q++) {
            struct listNode *temp1 = *curr;
            struct listNode *temp2 = temp1->next;
            // If temp1 > temp2 swap them
            if (temp1->ch > temp2->ch) {
                // Update the link after swapping
                *curr = swap(temp1, temp2);
                swapped = true;
            }
            // Move the current pointer to the next node
            curr = &(*curr)->next;
        }
        // If any pair of elements is not swapped, break the loop.
        if (swapped == false)
            break;
    }
}
// adding nodes to the linked list
void addNode(struct listNode **start, int ch) {
    // creating a new node
    struct listNode *temp = new struct listNode();
    // add ch to the node
    temp->ch = ch;
    temp->next = NULL;
    // If the list is empty, add a node to the list
    if (*start == NULL) {
        *start = temp;
    } else {
        // If the list has some nodes, append the node at the end of the list
        struct listNode *pointer1 = *start;
        while (pointer1->next != NULL) {
            pointer1 = pointer1->next;
        }
        pointer1->next = temp;
    }
}
// print nodes
void printLinkedList(struct listNode *head) {
    cout << "The sorted list is " << endl;
    while (head != NULL) {
        cout << char(head->ch) << " -> ";
        head = head->next;
    }
    cout << "NULL" << endl;
}
int main() {
    int arr[] = {'e', 's', 'a', 'x', 'c', 'e', 'f', 'p', 'b', 'n', 'a'};
    int len, p;
    // create an empty linked list
    struct listNode *start = NULL;
    len = sizeof(arr) / sizeof(arr[0]);
    // inserting characters of the array to a linked list
    for (p = 0; p < len; p++)
        addNode(&start, arr[p]);
    // Sort the list
    sortLinkedList(&start, len);
    printLinkedList(start);
    return 0;
}

输出

The sorted list is 
a -> a -> b -> c -> e -> e -> f -> n -> p -> s -> x -> NULL

时间复杂度 - O(N^2)，因为我们使用了两个嵌套循环。

空间复杂度 - O(1)，因为在sortLinkedList()函数中我们没有使用动态空间。然而，当我们将数组转换为链表时，我们使用了O(N)的空间，但这不是排序的一部分。

方法2

在这种方法中，我们将使用选择排序算法对链表进行排序。在选择排序算法中，我们从长度为len – p的后缀中找到包含最小值的节点。之后，我们将最小节点与第p个索引的节点进行交换。

步骤

步骤1 - 使用‘start’节点来定义并初始化‘current’节点。

步骤2 - 使用while循环，直到‘current’节点为null。

步骤3 - 用‘current’节点初始化‘minNode’，并用下一个current初始化‘traverse’，因为我们需要找到最小的节点。

步骤4 - 使用嵌套的while循环来找到最小的节点，并将其与‘current’节点进行交换。

步骤5 - 将current节点移动到下一个节点。

示例

#include <iostream>
using namespace std;

struct listNode {
    int ch;
    listNode* next;
};

void swapNodes(struct listNode* node1, struct listNode* node2) {
    int temp = node1->ch;
    node1->ch = node2->ch;
    node2->ch = temp;
}

void sortLinkedList(struct listNode* start) {
    struct listNode* current = start;
    while (current != nullptr) {
        struct listNode* minNode = current;
        struct listNode* traverse = current->next;
        while (traverse != nullptr) {
            if (traverse->ch < minNode->ch) {
                minNode = traverse;
            }
            traverse = traverse->next;
        }
        swapNodes(current, minNode);
        current = current->next;
    }
}

void addNode(struct listNode** start, int ch) {
    struct listNode* newNode = new struct listNode();
    newNode->ch = ch;
    newNode->next = nullptr;
    if (*start == nullptr) {
        *start = newNode;
    } else {
        struct listNode* current = *start;
        while (current->next != nullptr) {
            current = current->next;
        }
        current->next = newNode;
    }
}
void printLinkedList(struct listNode* head) {
    cout << "The sorted list is " << endl;
    while (head != nullptr) {
        cout << char(head->ch) << " -> ";
        head = head->next;
    }
    cout << "NULL" << endl;
}

int main() {
    int arr[] = {'e', 's', 'a', 'x', 'c', 'e', 'f', 'p', 'b', 'n', 'a'};
    int len = sizeof(arr) / sizeof(arr[0]);
    struct listNode* start = nullptr;
    for (int p = 0; p < len; p++) {
        addNode(&start, arr[p]);
    }
    sortLinkedList(start);
    printLinkedList(start);
    return 0;
}

输出

The sorted list is 
a -> a -> b -> c -> e -> e -> f -> n -> p -> s -> x -> NULL

时间复杂度 − O(N^2) ，因为我们使用了两个嵌套的while循环。

空间复杂度 − O(1) ，因为我们没有使用动态空间。