C++设单链表以非递减有序排列，设计算法实现在单链表中删去值相同的多余结点

在C++中，如果给定一个单链表，其元素已经按照非递减顺序排列，我们可以设计一种算法来删除所有重复的元素，只保留每个值的第一个出现。这种操作通常称为“去重”或“唯一化”。以下是一个简单的示例算法：

#include <iostream>
using namespace std;

// 链表节点定义
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 去除链表中重复的元素
ListNode* removeDuplicates(ListNode* head) {
    if (head == nullptr || head->next == nullptr) {
        return head;
    }

    ListNode* current = head;
    while (current->next != nullptr) {
        if (current->val > current->next->val) {
            // 将当前节点的next指向下一个重复元素，跳过重复部分
            current->next = current->next->next;
        } else {
            current = current->next;
        }
    }
    return head;
}

// 打印链表
void printList(ListNode* head) {
    ListNode* temp = head;
    while (temp != nullptr) {
        cout << temp->val << " ";
        temp = temp->next;
    }
    cout << endl;
}

int main() {
    // 示例链表：1->1->2->3->3->3->4->4->4
    ListNode* head = new ListNode(1);
    head->next = new ListNode(1);
    head->next->next = new ListNode(2);
    head->next->next->next = new ListNode(3);
    head->next->next->next->next = new ListNode(3);
    head->next->next->next->next->next = new ListNode(3);
    head->next->next->next->next->next->next = new ListNode(4);
    head->next->next->next->next->next->next->next = new ListNode(4);
    head->next->next->next->next->next->next->next->next = new ListNode(4);

    cout << "Original List: ";
    printList(head);

    head = removeDuplicates(head);

    cout << "List after removing duplicates: ";
    printList(head);

    return 0;
}

上述代码首先检查头节点是否存在，以及是否只有一个元素。然后遍历整个链表，遇到较小的值时，就直接跳过它，直到找到下一个大于等于当前值的元素。这样做保证了链表始终保持非递减有序，并移除了所有重复的元素。