首页C++写一算法将单链表中值重复的结点删除，使所得的结果链表中所有结点的值均不相同。

C++写一算法将单链表中值重复的结点删除，使所得的结果链表中所有结点的值均不相同。

时间: 2024-09-20 14:16:44 浏览: 146

在C++中，可以使用双指针（快慢指针）的方式来解决这个问题。以下是简单的步骤： ```cpp // 定义链表节点结构体 struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {} }; void removeDuplicates(ListNode* head) { if (head == nullptr || head->next == nullptr) { return; // 如果链表为空或只有一个元素，无需处理 } ListNode* slow = head; ListNode* fast = head->next; while (fast != nullptr && fast->next != nullptr) { // 当两个指针都未到达链表尾部 if (fast->val == slow->val) { // 如果当前节点的值等于下一个节点，就跳过这个重复的节点 fast = fast->next; } else { // 否则，移动慢指针前进 slow = slow->next; } fast = fast->next; // 快指针总是比慢指针多走一步 } if (fast != nullptr && fast->val == slow->val) { // 检查是否需要删除最后一个节点 slow->next = fast->next; } } ``` 这个算法的工作原理是：慢指针每次走一步，而快指针每次走两步。当快指针遇到重复值时，它会直接越过该节点。当快指针到达链表尾部时，慢指针的位置就是新链表的结尾，之前的重复节点已经被删除。

阅读全文