使用递归从已排序的链表中删除重复项

1. 简介

链表是一种基础的数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。链表可以分为单向链表和双向链表，其中双向链表比单向链表多了一个指向前一个节点的指针。链表相对于数组的优点是可以高效地进行增删操作，但是由于链表中的元素不是按顺序存储的，因此在链表中查找某个元素的效率比在数组中低。

本文将介绍如何使用递归的方法从已排序的单向链表中删除重复的元素。为了便于阅读，本文假设所操作的链表中不包含重复的元素，即为一个已排序的单调递增链表。

2. 算法思路

我们可以从链表的第一个节点开始遍历链表，如果当前节点的值和下一个节点的值相同，那么就将当前节点的next指针指向下一个节点的下一个节点，即跳过下一个节点。

具体来说，可以定义一个递归函数removeDuplicates(ListNode* head)来实现链表中删除重复元素的操作。该函数的基本思路是：如果当前节点和下一个节点的值相同，则将当前节点的next指针指向下一个节点的next节点，并递归调用removeDuplicates函数。

2.1 递归终止条件

递归函数必须要有一个终止条件，否则就会形成无限递归，导致程序崩溃。对于removeDuplicates函数来说，终止条件是当前节点或下一个节点为空，即已经遍历到链表的末尾了。

2.2 递归过程

递归过程需要完成的任务是删除重复的节点。具体地，我们可以定义两个指针，一个指向当前节点，另一个指向下一个节点。如果当前节点的值和下一个节点的值相同，则将当前节点的next指向下一个节点的next节点，跳过下一个节点即可。否则，仅需递归调用removeDuplicates函数，将下一个节点作为参数传入。

3. 代码实现

typedef struct ListNode {

    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};
ListNode* removeDuplicates(ListNode* head) {
    if (head == NULL || head->next == NULL)
        return head;
    ListNode* nextNode = head->next;
    if (head->val == nextNode->val) {
        head->next = nextNode->next;
        delete nextNode;
        return removeDuplicates(head);
    }
    else {
        head->next = removeDuplicates(nextNode);
        return head;
    }
}

4. 测试

为了测试上述代码是否正确，我们可以编写一个函数printList(ListNode* head)，用来打印链表中的值。具体实现方式是从头节点开始，依次输出每个节点的值，直到遇到空节点为止。

为了测试removeDuplicates函数的效果，我们可以构造一个含有重复元素的链表，然后将其传入removeDuplicates函数中进行测试。

void printList(ListNode* head) {

    ListNode* curr = head;
    while (curr != NULL) {
        cout << curr->val << " ";
        curr = curr->next;
    }
}
int main() {
    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);
    cout << "Original list: ";
    printList(head);
    cout << endl;
    cout << "List after removing duplicates: ";
    head = removeDuplicates(head);
    printList(head);
    cout << endl;
    return 0;
}

经过测试，该代码输出的结果为：

Original list: 1 1 2 3 3

List after removing duplicates: 1 2 3

5. 总结

本文介绍了如何使用递归的方法从已排序的单向链表中删除重复的元素。需要注意的是，由于递归函数需要不断调用自身，因此可能会导致栈溢出的风险。为了避免这种情况的发生，可以通过尾递归、迭代等方式来优化递归算法。

在实际的软件开发中，链表数据结构的应用非常广泛，例如用于实现数据库的索引、缓存机制等。因此，熟练掌握链表的操作和具体实现方式具有十分重要的意义。