已知非空线性链表第1个链结点指针为list，链结点构造为 struct node{ datatype data; node *link; }; 请写一算法，将该链表中数据域值最大的那个点移到链表的最后面。（假设链表中数据域值最大的链结点惟一）（注意：要求先写出算法的解题思路，然后再写出算法） 【输入形式】 输入为一个整数序列，整数之间以空格隔开，序列以回车结尾。 【输出形式】 输出为移动后的整数序列，整数之间以空格隔开，序列以回车结尾。 【样例输入】 3 12 4 9 5 1 【样例输出】 3 4 9 5 1 12 【样例说明】 将序列中最大的数字12移动到序列最后。 【评分标准】 本题必须采用链表来实现移动操作 ，其他方法不得分。

算法思路：

1.先找到链表中数据域值最大的那个点，记录它的指针max_node和它前驱结点指针pre。

2.将该点从链表中摘下来，即pre->link = max_node->link。

3.将max_node插入到链表的最后面，即找到链表最后一个结点，让它的link指向max_node。

4.最后输出整个链表即可。

算法实现：

#include <iostream>
using namespace std;

struct node{
    int data;
    node *link;
};

int main()
{
    node *list = new node;
    node *p = list;
    cin >> p->data;
    while(cin.get() != '\n'){
        p->link = new node;
        p = p->link;
        cin >> p->data;
    }
    p->link = nullptr;

    node *max_node = list, *pre_max = nullptr, *last_node = list;
    //寻找最大节点
    for(node *temp = list; temp != nullptr; temp = temp->link){
        if(temp->data > max_node->data){
            max_node = temp;
        }
    }
    //寻找最后节点
    while(last_node->link != nullptr){
        last_node = last_node->link;
    }
    //找出max节点前驱节点pre
    if(max_node != list){
        for(node *temp = list; temp != nullptr; temp = temp->link){
            if(temp->link == max_node){
                pre_max = temp;
                break;
            }
        }
    }

    if(max_node != last_node){//如果max_node在中间
        if(pre_max == nullptr){//max_node在第一个
            list = max_node->link;
            last_node->link = max_node;
            max_node->link = nullptr;
        }
        else{//max_node在链表中间
            pre_max->link = max_node->link;
            last_node->link = max_node;
            max_node->link = nullptr;
        }
    }

    //输出链表
    for(node *temp = list; temp != nullptr; temp = temp->link){
        cout << temp->data << " ";
    }
    cout << endl;

    return 0;
}