请写一算法,将该链表中数据域值最大的那个点移到链表的最后面。
时间: 2023-06-11 16:08:27 浏览: 97
假设链表节点的数据结构如下:
```
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
```
以下是将链表中数据域值最大的节点移到最后面的算法:
```
ListNode* moveMaxNodeToTail(ListNode* head) {
if (!head || !head->next) {
return head;
}
ListNode* maxNode = head;
ListNode* preMaxNode = nullptr;
ListNode* curNode = head;
// 找到数据域值最大的节点及其前驱节点
while (curNode) {
if (curNode->val > maxNode->val) {
maxNode = curNode;
preMaxNode = head;
} else if (curNode->val == maxNode->val) {
preMaxNode = curNode;
}
curNode = curNode->next;
}
// 如果数据域值最大的节点不在链表的末尾,则将其移到末尾
if (maxNode->next) {
ListNode* tail = maxNode;
while (tail->next) {
tail = tail->next;
}
tail->next = maxNode;
preMaxNode->next = maxNode->next;
maxNode->next = nullptr;
}
return head;
}
```
该算法的时间复杂度为 $O(n)$,其中 $n$ 是链表的长度。
阅读全文