从已排序的双向链表中删除重复元素

在之前的文章中，我们已经探讨过如何从已排序的单向链表中删除重复节点。现在，让我们将目光转向数据结构稍作变动的情况：已排序的双向链表。

本文的目标是编写一个函数，用于删除已排序双向链表中的所有重复节点，使每个元素在链表中仅出现一次。

题目详解

输入： 一个已排序的双向链表。
输出： 一个与输入链表结构一致，但所有重复节点已被移除的链表。

方法一：迭代法（线性遍历）

处理该问题的“迭代法”非常直观，这得益于链表是已排序的。由于所有重复的节点在链表中必定是相邻的，我们只需要遍历链表，逐个比较当前节点与下一个节点的数据即可。这与我们处理单向链表时的逻辑非常相似。

算法思路：

• 我们从链表的头部（Head）开始遍历。
• 当我们还有当前节点以及下一个节点可以比较时（即 INLINECODE12888eb4 和 INLINECODEc5a87e2d 都不为空），我们执行以下循环：

* 如果发现 INLINECODE0034200e 节点的数据与 INLINECODE7bfe7154 节点的数据相同，说明遇到了重复项。

* 为了删除 INLINECODE177064a2（那个重复的节点），我们需要调整指针：将 INLINECODE71a3c979 指向 INLINECODEd1ed9037。如果 INLINECODEe9644cf1 存在，别忘了将其 INLINECODE3c4c4867 指针指回 INLINECODEc1f307bc，以维护双向链表的完整性。

* 如果数据不同，则只需将 INLINECODE8b56f621 指针向前移动到 INLINECODEe9744768，继续检查后续节点。

• 当遍历结束时，链表中的所有重复项都已被移除。

C++ 代码实现：

// C++ program to remove duplicates
// from a sorted doubly linked list
#include 
using namespace std;

class Node {
public:
    int data;
    Node* next;
    Node* prev;
};

// Function to delete a node in a Doubly Linked List.
// head_ref --> pointer to head node pointer.
// del -->  pointer to node to be deleted.
void deleteNode(Node** head_ref, Node* del)
{
    // base case
    if (*head_ref == NULL || del == NULL)
        return;

    // If node to be deleted is head node
    if (*head_ref == del)
        *head_ref = del->next;

    // Change next only if node to be deleted
    // is NOT the last node
    if (del->next != NULL)
        del->next->prev = del->prev;

    // Change prev only if node to be deleted
    // is NOT the first node
    if (del->prev != NULL)
        del->prev->next = del->next;

    // Finally, free the memory occupied by del
    free(del);
}

// Function to remove duplicates from a sorted doubly linked list
void removeDuplicates(Node** head_ref)
{
    // if list is empty
    if ((*head_ref) == NULL)
        return;

    Node* current = *head_ref;
    Node* next;

    // traverse the list till the last node
    while (current->next != NULL) {

        // Compare current node with the next node
        if (current->data == current->next->data)
            // delete the node pointed to by ‘current->next‘
            deleteNode(head_ref, current->next);
        else
            // move to the next node if no duplicate is found
            current = current->next;
    }
}

// Function to insert a node at the beginning of the Doubly Linked List
void push(Node** head_ref, int new_data)
{
    // allocate node
    Node* new_node = (Node*)malloc(sizeof(Node));

    // put in the data
    new_node->data = new_data;

    // since we are adding at the beginning,
    // prev is always NULL
    new_node->prev = NULL;

    // link the old list off the new node
    new_node->next = (*head_ref);

    // change prev of head node to new node
    if ((*head_ref) != NULL)
        (*head_ref)->prev = new_node;

    // move the head to point to the new node
    (*head_ref) = new_node;
}

// Function to print nodes in a given doubly linked list
void printList(Node* node)
{
    while (node != NULL) {
        cout <data <next;
    }
}

// Driver program to test above functions
int main()
{
    Node* head = NULL;

    // Create the doubly linked list:
    // 88655322
    push(&head, 2);
    push(&head, 2);
    push(&head, 3);
    push(&head, 5);
    push(&head, 5);
    push(&head, 6);
    push(&head, 8);
    push(&head, 8);

    cout << "Original Doubly Linked List:
";
    printList(head);

    // remove duplicates
    removeDuplicates(&head);

    cout << "
Doubly Linked List after removing duplicates:
";
    printList(head);

    return 0;
}

复杂度分析：

• 时间复杂度： O(n)，其中 n 是链表中节点的数量。我们只需要遍历一次链表。
• 空间复杂度： O(1)。我们只使用了常数级别的额外空间（指针变量），没有使用额外的数据结构。

方法二：递归法（备用方案）

除了迭代法，我们还可以使用递归来解决这个问题。虽然这种方法的思路也很巧妙，但在处理非常长的链表时，可能会受到递归调用栈深度的限制。

算法思路：

• 递归终止条件： 如果链表为空，或者只有一个节点（即 INLINECODE457be63a 为空或 INLINECODE6f62ae3f 为空），则直接返回 head，因为没有重复项可以处理。
• 处理重复项： 检查头节点的值是否等于下一个节点的值 (head->data == head->next->data)。

* 如果是，这意味着接下来的节点都是重复的。我们需要保存当前的 INLINECODE019c0302 指针，并递归调用函数处理 INLINECODEc377645b（跳过下一个节点）。

* 在递归调用返回后，我们将得到的链表（假设为 INLINECODE614bde8f）连接到保存的 INLINECODEdb1aa4ab 节点上，并返回 head。

• 无重复项的情况： 如果头节点的值不等于下一个节点的值，说明当前节点是唯一的。我们只需递归处理剩下的链表 (INLINECODE98ef76e9)，并将返回的节点连接到当前 INLINECODEbcf915a3 上，最后返回 head。

这种方法本质上是“反向思考”，从链表的末尾开始处理并向上层返回结果。

C++ 代码实现（递归版）：

// C++ implementation to remove duplicates from a
// sorted doubly linked list using recursion
#include 
using namespace std;

// Node of the doubly linked list
struct Node {
    int data;
    Node *next, *prev;
};

// Function to remove duplicates from a sorted doubly linked list
Node* removeDuplicates(Node* head)
{
    // Base case: if list is empty or has only one node
    if (head == nullptr || head->next == nullptr)
        return head;

    // If current node is a duplicate
    if (head->data == head->next->data) {
        Node* temp = head;
        // Recursive call for the node after the next
        Node* res = removeDuplicates(head->next->next);
        
        // Ensure proper linkage
        if (res != nullptr) {
            res->prev = temp;
        }
        temp->next = res;
        return temp;
    }
    else {
        // If current node is unique, move to next
        Node* res = removeDuplicates(head->next);
        if (res != nullptr) {
            res->prev = head;
        }
        head->next = res;
        return head;
    }
}

// Utility function to create a new node
Node* newNode(int data)
{
    Node* node = new Node;
    node->data = data;
    node->prev = node->next = nullptr;
    return node;
}

// Utility function to append a node at the end of the list
void append(Node** headRef, int data)
{
    Node* newNode = new Node;
    newNode->data = data;
    newNode->next = nullptr;

    if (*headRef == nullptr) {
        newNode->prev = nullptr;
        *headRef = newNode;
        return;
    }

    Node* last = *headRef;
    while (last->next != nullptr)
        last = last->next;

    last->next = newNode;
    newNode->prev = last;
}

// Utility function to print the list
void printList(Node* node)
{
    while (node != nullptr) {
        cout <data <next;
    }
}

// Driver code
int main()
{
    Node* head = nullptr;

    // Create the doubly linked list:
    // 88655322
    append(&head, 8);
    append(&head, 8);
    append(&head, 6);
    append(&head, 5);
    append(&head, 5);
    append(&head, 3);
    append(&head, 2);
    append(&head, 2);

    cout << "Original Doubly Linked List:
";
    printList(head);

    head = removeDuplicates(head);

    cout << "
Doubly Linked List after removing duplicates:
";
    printList(head);

    return 0;
}

复杂度分析（递归版）：

• 时间复杂度： O(n)，每个节点都会被访问一次。
• 空间复杂度： O(n)，这是由于递归调用栈所消耗的空间。在最坏情况下（链表很长），栈的深度会等于链表的长度。

结论：

通常情况下，我们推荐使用迭代法。因为它不仅逻辑简单，而且空间复杂度为 O(1)，在处理大规模数据时更加稳定和高效。递归法虽然体现了“分而治之”的思想，但在生产环境中使用时需要谨慎考虑栈溢出的风险。

相关问题

为了进一步巩固你对链表操作的理解，你可以尝试解决以下相关问题：

• 从未排序的链表中删除重复元素：这个问题可以使用哈希表或双重循环来解决。
• 删除链表中所有出现特定值的节点。
• 在链表中删除重复节点（保留最后一次出现的节点）。