C++实现LeetCode(83.移除有序链表中的重复项)

下面是关于“C++实现LeetCode(83.移除有序链表中的重复项)”的完整攻略。

题目描述

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例1:

输入: 1->1->2
输出: 1->2

示例2:

输入: 1->1->2->3->3
输出: 1->2->3

解题思路

由于链表已经是有序的，所以我们只需要顺序遍历链表，在遍历的过程中判断哪些节点需要删除即可。

具体而言，我们定义一个指针 p，指向链表的当前节点。接着，我们开始循环，进行遍历。在每一个节点 p 身上，如果存在下一个节点，且下一个节点的值和当前节点的值相等，那么我们就需要将下一个节点删除。这里需要注意，删除操作需要保证链表中前后关系的规范，也就是说，需要让当前节点的下一个节点，指向下下一个节点。如果链表的头节点需要被删除，我们可以重新定义头节点为第二个节点。

解题代码

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == NULL) {
            return head;
        }
        ListNode* p = head;
        while (p->next != NULL) {
            if (p->val == p->next->val) {
                ListNode* temp = p->next;
                p->next = p->next->next;
                delete temp;
            } else {
                p = p->next;
            }
        }
        return head;
    }
};

示例说明

我们可以通过两个不同的示例来说明这段代码的运行。

首先是下面这个示例：

输入：1 -> 1 -> 2 -> 3 -> 3
输出：1 -> 2 -> 3

在这个示例中，由于存在 1 和 3 两个数值出现了重复，因此我们需要删除第二个 1 和第二个 3。具体而言，我们可以在第一个 1 上，判断它的下一个节点是否为相同的数值，由于下一个节点是 1，因此需要删除下一个节点。此时链表变为 1 -> 2 -> 3 -> 3。我们继续判断第一个 3，它的下一个节点是 3，因此需要删除下一个节点。最终，返回的链表为 1 -> 2 -> 3。

接下来是另一个示例：

输入: 1->1->1->2->2->3->4->5->5->6
输出: 1->2->3->4->5->6

在这个示例中，由于存在多个相同的数值，我们需要删除它们，最终返回的是不包含重复节点的链表。在这个示例中，我们首先判断第一个 1，发现它的下一个节点也为 1，因此需要删除下一个节点。此时链表变为 1 -> 2 -> 2 -> 3 -> 4 -> 5 -> 5 -> 6。我们继续判断第一个 2，发现它的下一个节点为相同的数值，需要删除下一个节点。同样的方式，我们将相同的节点删除后，最终返回的链表为 1 -> 2 -> 3 -> 4 -> 5 -> 6。