c++通过建立linklist.h文件将一个列表中的负数放在非负数之前

Question

已建立linklist.h文件，将负数按原来顺序列表负数顺序放在非负数之前。

Answer 1

2302_79603878 下午好🌅🌅🌅
本答案参考ChatGPT-3.5

算法设计思想：

• 遍历链表，将负数结点和非负数结点分别存放到两个新的链表中。
• 最后将负数链表的尾部指向非负数链表的头部，形成新的链表。

实现算法的步骤：

1. 定义两个指针，一个用于遍历原链表，一个用于遍历负数链表。
2. 创建两个新的链表，一个用于存放负数结点，一个用于存放非负数结点。
3. 遍历原链表，如果结点数据域为负数，则将该结点插入负数链表末尾；如果结点数据域为非负数，则将该结点插入非负数链表末尾。
4. 将负数链表的尾部指向非负数链表的头部。
5. 返回新的链表。

时间复杂度分析： 遍历原链表的时间复杂度为O(n)，其中n为链表的长度。没有使用额外的数据结构，所以空间复杂度为O(1)。

以下是具体的代码实现：

#include <iostream>
using namespace std;

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

Node* moveNegativeBeforeNonNegative(Node* head) {
    Node* p = head->next;
    Node* negativeHead = new Node();
    Node* negativeTail = negativeHead;
    Node* nonNegativeHead = new Node();
    Node* nonNegativeTail = nonNegativeHead;

    while (p != nullptr) {
        if (p->data < 0) {
            negativeTail->next = p;
            negativeTail = negativeTail->next;
        } else {
            nonNegativeTail->next = p;
            nonNegativeTail = nonNegativeTail->next;
        }
        p = p->next;
    }

    negativeTail->next = nonNegativeHead->next;
    nonNegativeTail->next = nullptr;

    head->next = negativeHead->next;

    delete negativeHead;
    delete nonNegativeHead;

    return head;
}

// 测试代码
void printList(Node* head) {
    Node* p = head->next;
    while (p != nullptr) {
        cout << p->data << " ";
        p = p->next;
    }
    cout << endl;
}

int main() {
    Node* head = new Node();  // 头结点
    Node* p = head;
    int arr[] = {1, -2, 3, -4, 5};  // 测试数据
    int n = sizeof(arr) / sizeof(arr[0]);

    for (int i = 0; i < n; i++) {
        Node* newNode = new Node();
        newNode->data = arr[i];
        newNode->next = nullptr;

        p->next = newNode;
        p = p->next;
    }

    cout << "原链表：";
    printList(head);

    head = moveNegativeBeforeNonNegative(head);

    cout << "调整后的链表：";
    printList(head);

    return 0;
}

希望可以帮助到你，如果有其他问题，请继续提问。