C++ 实现L2-002 链表去重

C++ 实现 L2-002 链表去重的完整攻略：

1. 链表的数据结构

在开始实现 L2-002 链表去重之前，我们需要实现一个链表的数据结构。链表是一种数据结构，用于存储一系列的元素，并且可以动态地添加或删除该链表中的元素。

在 C++ 中，可以使用结构体或类来实现链表的数据结构。一个链表的结构体应该至少包含两个属性：节点数据和指向下一个节点的指针。在链表中，每个节点都会指向下一个节点，直到最后一个节点指向 NULL。

示例代码：

struct ListNode {
    int val; // 节点数据
    ListNode *next; // 指向下一个节点的指针
    ListNode(int x) : val(x), next(NULL) {} // 构造函数，用于初始化节点数据和指针
};

1. 链表去重

在实现链表去重之前，需要对链表进行排序，以便后续去重时只需要比较相邻的节点。链表可以使用插入排序或者归并排序进行排序，这里我们使用归并排序。

示例代码：

// 归并排序
ListNode* sortList(ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    ListNode *slow = head, *fast = head->next;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    ListNode *right = sortList(slow->next);
    slow->next = NULL;
    ListNode *left = sortList(head);
    return mergeList(left, right);
}

// 合并两个有序链表
ListNode* mergeList(ListNode* l1, ListNode* l2) {
    ListNode *dummy = new ListNode(0);
    ListNode *prev = dummy;
    while (l1 != NULL && l2 != NULL) {
        if (l1->val < l2->val) {
            prev->next = l1;
            l1 = l1->next;
        } else {
            prev->next = l2;
            l2 = l2->next;
        }
        prev = prev->next;
    }
    if (l1 != NULL) {
        prev->next = l1;
    }
    if (l2 != NULL) {
        prev->next = l2;
    }
    return dummy->next;
}

// 链表去重
ListNode* deleteDuplicates(ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }
    ListNode *cur = head;
    while (cur != NULL && cur->next != NULL) {
        if (cur->val == cur->next->val) {
            ListNode *tmp = cur->next;
            cur->next = cur->next->next;
            delete tmp;
        } else {
            cur = cur->next;
        }
    }
    return head;
}

在使用归并排序对链表进行排序之后，我们可以使用一个指针 cur 依次遍历链表。对于每个节点，如果它与后一个节点的值相同，就删除后一个节点，并更新指针；否则，继续向下遍历。

1. 示例说明

以下是两个示例说明。

示例 1：

假设有一个链表：1 -> 2 -> 2 -> 3 -> 4 -> 4 -> 5

首先，使用归并排序对链表进行排序，得到：1 -> 2 -> 2 -> 3 -> 4 -> 4 -> 5

接下来，使用指针 cur 遍历链表，当 cur 指向节点 2 时，发现它与后一个节点 2 的值相同，因此删除节点 2 并且更新指针，得到链表：1 -> 2 -> 3 -> 4 -> 4 -> 5

继续遍历，当 cur 指向节点 4 时，发现它与后一个节点 4 的值相同，因此删除节点 4 并且更新指针，得到链表：1 -> 2 -> 3 -> 4 -> 5

最终得到的链表为：1 -> 2 -> 3 -> 4 -> 5

示例 2：

假设有一个链表：1 -> 1 -> 1 -> 2 -> 3

首先，使用归并排序对链表进行排序，得到：1 -> 1 -> 1 -> 2 -> 3

接下来，使用指针 cur 遍历链表，当 cur 指向节点 1 时，发现它与后一个节点 1 的值相同，因此删除节点 1 并且更新指针，得到链表：1 -> 2 -> 3

继续遍历，当 cur 指向节点 2 时，发现它与后一个节点 3 的值不相同，因此继续向下遍历。

最终得到的链表为：1 -> 2 -> 3

以上就是 C++ 实现 L2-002 链表去重的攻略，希望能对你有所帮助。

阅读剩余 59%