【8.5】链表-删除排序链表中的重复元素

一、题目

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

示例 1：

输入：head = [1,1,2]
输出：[1,2]

示例 2：

输入：head = [1,1,2,3,3]
输出：[1,2,3]

提示：

• 链表中节点数目在范围 [0, 300] 内
• -100 <= Node.val <= 100
• 题目数据保证链表已经按升序 排列

二、解题思路

2.1 使用一个指针解决       

        这道题目中提到，链表中的节点值是按照升序排列的。既然链表是有序的，那么值相同的节点一定是相邻的。我们可以使用一个指针 `cur` 来遍历链表，每次判断当前节点 `cur` 的值是否与下一个节点的值相同。如果相同，就将下一个节点删除。接下来，我们以示例 2 为例，来展示具体的操作过程。

#include <iostream>

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

ListNode* deleteDuplicates(ListNode* head) {
    // 如果当前节点是空，或者是单个节点，直接返回
    if (head == nullptr || head->next == nullptr)
        return head;

    // 只用一个指针 cur 指向当前节点
    ListNode* cur = head;
    while (cur->next != nullptr) {
        // 如果当前节点的值和下一个节点的值相同，
        // 就把下一个节点删除
        if (cur->val == cur->next->val) {
            cur->next = cur->next->next;
        } else {
            // 否则 cur 就往后移一步
            cur = cur->next;
        }
    }
    return head;
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    ListNode* curr = head;
    while (curr != nullptr) {
        std::cout << curr->val << " ";
        curr = curr->next;
    }
    std::cout << std::endl;
}

int main() {
    // 创建一个示例链表：1 -> 1 -> 2 -> 3 -> 3
    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);

    // 调用 deleteDuplicates 函数
    ListNode* result = deleteDuplicates(head);

    // 打印结果链表
    printList(result);

    return 0;
}

2.2 递归解决

        除了前面提到的使用单个指针的方法外，我们还可以通过递归的方式来解决这个问题。递归的实现需要对链表的逆序访问有一定的理解，如果你对链表的逆序操作不太熟悉，可以参考“倒序打印链表”的相关内容。接下来，我们以示例 1 为例，通过一个图示来详细说明递归的具体过程。

#include <iostream>

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

ListNode* deleteDuplicates(ListNode* head) {
    // 递归的边界条件判断
    if (head == nullptr || head->next == nullptr)
        return head;

    // 递归，相当于从后往前遍历
    head->next = deleteDuplicates(head->next);

    // 如果当前节点和下一个节点值相同，直接返回下一个节点，
    // 否则返回当前节点
    return head->val == head->next->val ? head->next : head;
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    ListNode* curr = head;
    while (curr != nullptr) {
        std::cout << curr->val << " ";
        curr = curr->next;
    }
    std::cout << std::endl;
}

int main() {
    // 创建一个示例链表：1 -> 1 -> 2 -> 3 -> 3
    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);

    // 调用 deleteDuplicates 函数
    ListNode* result = deleteDuplicates(head);

    // 打印结果链表
    printList(result);

    return 0;
}