如何在C++中删除有序链表的重复节点？ |21xrx.com

如何在C++中删除有序链表的重复节点？

2023-07-04 04:30:11 深夜i -- --

C++ 有序链表删除重复节点

在C++中删除重复节点是一种常见的链表操作，尤其是对于有序链表来说。因为有序链表中的元素是按照一定顺序排列的，因此当出现相同元素时，我们可以直接删除重复的元素，以保持链表有序性。下面我们将介绍在C++中如何实现删除有序链表的重复节点。

步骤1：定义链表节点

在开始操作有序链表之前，我们需要先定义链表节点的数据类型。通常我们使用以下的结构体来表示链表节点：


struct ListNode {
  int val;
  ListNode *next;
  ListNode(int x) : val(x), next(NULL) {}
};

其中，ListNode表示链表节点的类型，包含一个整数val和指向下一个节点的指针next。通过构造函数可以为每个节点赋初值，如上述代码中的val(x)和next(NULL)。

步骤2：遍历链表删除重复节点

接下来，我们可以使用两个指针来遍历链表，并删除重复节点。我们定义两个指针p和q，其中p指向当前节点，q指向p的下一个节点。我们在遍历链表的过程中，每当p和q节点的值相同时，就将q节点删除，并将p的next指针指向下一个节点。如果p和q节点的值不相同时，则将p后移一位，q也随之后移一位，继续遍历链表。

以下是C++代码实现：


ListNode* deleteDuplicates(ListNode* head) {
  ListNode* p = head;
  while (p != NULL) {
    ListNode* q = p->next;
    while (q != NULL && p->val == q->val)
      p->next = q->next;
      delete q;
      q = p->next;
    
    p = p->next;
  }
  return head;
}

需要注意的是，在删除重复节点时，我们需要使用delete关键字将q指针所指向的节点空间回收，以避免内存泄漏。

步骤3：测试代码

我们可以使用以下C++代码来测试上述删除重复节点的函数：


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);
  ListNode* result = deleteDuplicates(head);
  ListNode* p = result;
  while (p != NULL)
    cout << p->val << " ";
    p = p->next;
  
  return 0;
}

运行上述代码后，输出结果为1 2 3，表示已成功删除重复节点。

总结

在C++中删除有序链表的重复节点需要使用两个指针p和q遍历链表，通过比较p和q节点的值来判断是否有重复节点，并将重复节点删除。代码实现简单易懂，但需要注意内存泄漏问题。在实际应用中，我们可以根据具体情况进行优化，使代码更加高效。

上一篇: idea打包java可执行jar包

下一篇: C++类变量简介

评论区

()

相似文章