【问题描述】 已知非空线性链表第1个链结点指针为list，链结点构造为 struct node{ datatype data; node *link; }; 请写一算法，将该链表中数据域值最大的那个点移到链表的最后面。（假设链表中数据域值最大的链结点惟一）（注意：要求先写出算法的解题思路，然后再写出算法） 【输入形式】 输入为一个整数序列，整数之间以空格隔开，序列以回车结尾，输入-1结束（假设链表中吴数据-1）。 【输出形式】 输出为移动后的整数序列，整数之间以空格隔开，序列以回车结尾。 【样例输入】 3 12 4 9 5 1 -1 【样例输出】 3 4 9 5 1 12 【样例说明】 将序列中最大的数字12移动到序列最后。 用c++写

以下是解题思路和 C++ 代码实现： 解题思路： 1. 首先遍历链表，找到数据域值最大的链结点以及其前一个链结点。 2. 如果最大节点不是链表的尾节点，将其从当前位置删除，并插入到链表的末尾。 ```cpp #include <iostream> using namespace std; struct Node { int data; Node* link; Node(int x) : data(x), link(NULL) {} }; // 查找最大节点及其前一个节点 void findMaxAndPrev(Node* list, Node*& maxNode, Node*& prevMax) { Node* curr = list; maxNode = list; prevMax = NULL; Node* prev = NULL; while (curr!= NULL) { if (curr->data > maxNode->data) { maxNode = curr; prevMax = prev; } prev = curr; curr = curr->link; } } // 将最大节点移到链表末尾 void moveMaxToEnd(Node*& list) { Node* maxNode = NULL; Node* prevMax = NULL; findMaxAndPrev(list, maxNode, prevMax); if (maxNode!= NULL && prevMax!= NULL) { prevMax->link = maxNode->link; Node* curr = list; while (curr->link!= NULL) { curr = curr->link; } curr->link = maxNode; maxNode->link = NULL; } } // 打印链表 void printList(Node* list) { Node* curr = list; while (curr!= NULL) { cout << curr->data << " "; curr = curr->link; } cout << endl; } // 构建链表 Node* buildList() { int num; cin >> num; Node* head = NULL; Node* tail = NULL; while (num!= -1) { Node* newNode = new Node(num); if (head == NULL) { head = newNode; tail = newNode; } else { tail->link = newNode; tail = newNode; } cin >> num; } return head; } int main() { Node* list = buildList(); moveMaxToEnd(list); printList(list); return 0; } ``` [2024-10-14 22:52:26 | AI写代码神器 | 583点数解答]