已知非空单链表L, 请写一算法,将该链表中数据域值最大的那个点移到链表的最后面。(假设链表中数据域值最大的链结点惟一) 【输入形式】 元素个数 元素 整数之间以一个空格隔开,序列以回车结尾。 【输出形式】 输出为移动后的整数序列,整数之间以一个空格隔开,序列以回车结尾。 c++
时间: 2023-06-04 20:05:18 浏览: 101
抱歉,我可以回答你关于编程的问题。针对你的问题,以下是一种可能的解答:
算法思路:
1. 定义指针p和q,分别遍历单链表L。
2. 在遍历的过程中,用max记录数据域值最大的链结点的值,并用maxNode记录该结点的地址。
3. 遍历结束后,判断maxNode是否为链表的最后一个结点。如果是,直接返回链表即可。
4. 如果maxNode不是最后一个结点,则需要将其移动到最后一个结点的位置上。
5. 移动maxNode的方法是:先用temp指针记录maxNode的前一个结点的地址,然后利用链表的删除与插入操作重新构造链表。具体操作为:先将maxNode从链表中删除,然后将其插入到链表的尾部即可。
算法实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
Node* createList(int n); // 创建链表函数
void printList(Node *head); // 打印链表函数
Node* moveMaxNodeToEnd(Node *head); // 将最大节点移到最后的函数
int main() {
int n;
scanf("%d", &n);
Node *head = createList(n);
printf("原链表:\n");
printList(head);
head = moveMaxNodeToEnd(head);
printf("移动后的链表:\n");
printList(head);
return 0;
}
Node* createList(int n) {
Node *head = NULL, *tail = NULL;
for (int i = 0; i < n; i++) {
Node *newNode = (Node*) malloc(sizeof(Node));
scanf("%d", &(newNode->data));
newNode->next = NULL;
if (head == NULL) {
head = tail = newNode;
} else {
tail->next = newNode;
tail = newNode;
}
}
return head;
}
void printList(Node *head) {
Node *p = head;
while (p != NULL) {
printf("%d ", p->data);
p = p->next;
}
printf("\n");
}
Node* moveMaxNodeToEnd(Node *head) {
Node *maxNode = head, *p = head, *q = head->next;
while (q != NULL) {
if (q->data > maxNode->data) {
maxNode = q;
}
p = q;
q = q->next;
}
if (maxNode == p) {
return head;
}
Node *temp = head;
while (temp->next != maxNode) {
temp = temp->next;
}
temp->next = maxNode->next;
p->next = maxNode;
maxNode->next = NULL;
return head;
}
```
输入示例:
```
5
2 7 4 8 1
```
输出示例:
```
原链表:
2 7 4 8 1
移动后的链表:
2 7 4 1 8
```
希望能够帮到你!