带有头结点的非空单链表中结点数据域data均为整数，编写算法，将所有负数结点移动到非负数结点之前，要求移动前后所有负数（非负数）结点相对顺序不变。

Question

带有头结点的非空单链表中结点数据域data均为整数，编写算法将其中所有负数结点移动到非负数结点之前，要求移动前后所有负数结点相对顺序不变，所有非负数结点相对顺序不变。

（已经设置好了这样的.h文件，接下来怎么做？）

Answer 1

引自免费微信小程序：皆我百晓生

首先，我们需要创建一个辅助函数，将所有负数结点移动到非负数结点之前。我们可以使用一个临时变量来存储负数结点，然后遍历链表，将负数结点插入到非负数结点列表的头部。

以下是辅助函数的C++代码：

void moveNegativeToPositive(LinkNode*&head) {
    if (head == nullptr || head->next == nullptr) {
        return;
    }

    LinkNode *negativeHead = nullptr;
    LinkNode *current = head;

    while (current != nullptr && current->data < 0) {
        negativeHead = current;
        current = current->next;
    }

    if (negativeHead == nullptr) {
        return;
    }

    LinkNode *temp = negativeHead;
    while (temp->next != nullptr) {
        temp = temp->next;
    }

    temp->next = head;
    head = negativeHead->next;
    negativeHead->next = nullptr;
}

接下来，我们需要修改LinkList.h文件，以便在其中包含这个辅助函数。将以下代码添加到LinkList.h文件中：

#ifndef LINKLIST_H
#define LINKLIST_H

#include <stdio.h>

// 定义链表结点结构体
typedef struct Node {
    ElemType data;
    struct Node* next;
} Node;

// 辅助函数声明
void moveNegativeToPositive(Node*&head);

#endif // LINKLIST_H

最后，我们需要修改main.cpp文件，以便在创建链表时调用moveNegativeToPositive函数。在main.cpp文件中添加以下代码：

#include "LinkList.h"

int main() {
    LinkList list;

    // 添加数据元素
    if (!ListInsert(&list, 110, -5)) {
        printf("Error inserting element 110.\n");
        return 0;
    }

    // 添加数据元素
    if (!ListInsert(&list, 111, 3)) {
        printf("Error inserting element 111.\n");
        return 0;
    }

    // 打印链表
    printf("LinkList: ");
    Node* current = list.head;
    while (current != nullptr) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("nullptr\n");

    // 移动负数结点到非负数结点之前
    moveNegativeToPositive(&list.head);

    // 打印链表
    current = list.head;
    while (current != nullptr) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("nullptr\n");

    return 0;
}

现在，当你编译并运行程序时，它将创建一个带有头结点的非空单链表，并将其中所有负数结点移动到非负数结点之前。移动后的链表将如下所示：

-5 -> -10 -> 3 -> nullptr