首页 > 删除链表中的重复项

删除链表中的重复项

方法一：时间优先

建立一个hash_set，key为链表中已经遍历的节点内容，开始时为空。

从头开始遍历链表中的节点：

- 如果节点内容已经在hash_set中存在，则删除此节点，继续向后遍历；

- 如果节点内容不在hash_set中，则保留此节点，将节点内容添加到hash_set中，继续向后遍历。

这里STL没有hash_set，我直接用set实现的：





方法二：空间优先

解决的思路如下：

建立指针p，用于遍历链表；

建立指针q，q遍历p后面的结点，并与p数值比较；

建立指针r，r保存需要删掉的结点，再把需要删掉的结点的前后结点相接。由此去掉重复值。



下面是相关代码：

#include "list.h"
#include 
using namespace std;//借助STL中的set来删除链表中的重复项，比较高效（时间比中间更重要）
//建立STL中的set，key为链表中已经遍历的结点内容，开始时为空
//从头开始遍历链表中的结点：
//如果结点内容已经在set中存在，则删除此结点，继续向后遍历
//如果结点内容不在set中，则保留此结点，将结点内容添加到set中，继续向后遍历
ListNode* del_repeated_nodes(ListNode* pHead){if(pHead == NULL)return pHead;set KeySet;ListNode* pNewHead = pHead;ListNode* pCurNode = pHead;KeySet.insert(pHead->value);while(pCurNode->next){//已经存在则删除if(KeySet.count(pCurNode->next->value)){ListNode* pDelNode = pCurNode->next;pCurNode->next = pCurNode->next->next;delete pDelNode;}else{ //不存在则新增KeySet.insert(pCurNode->next->value);pCurNode = pCurNode->next;}}return pNewHead;
}//使用循环遍历方法：
//1.建立指针pNode，用于遍历链表
//2.建立指针pIterNode，用于遍历pNode之后的结点，并与pNode的值比较
//3.建立指针pDupNode，保存需要删除的结点，再把需要删除的结点的前后结点相接，由此去掉重复值
ListNode* del_duplicate_nodes(ListNode* pHead){ListNode* pNewHead = pHead;ListNode* pNode = pNewHead;while(pNode){//pNode用于遍历链表ListNode* pIterNode = pNode;while(pIterNode->next){//遍历pNode之后的结点，并与pIterNode的值比较if(pIterNode->next->value == pNode->value){ListNode* pDupNode = pIterNode->next;//保存要删除的值pIterNode->next = pIterNode->next->next;delete pDupNode;}elsepIterNode = pIterNode->next;}pNode = pNode->next;}return pNewHead;
}ListNode* Test(ListNode* pHead){printf("The original list is: 
");PrintList(pHead);//这里采用两种方法：前者空间占优，后者时间占优//ListNode* pNewHead = del_duplicate_nodes(pHead);ListNode* pNewHead = del_repeated_nodes(pHead);printf("The del duplicate list is: 
");PrintList(pNewHead);return pNewHead;
}void Test1(){ListNode* pNode1 = CreateListNode(1);ListNode* pNode2 = CreateListNode(1);ListNode* pNode3 = CreateListNode(2);ListNode* pNode4 = CreateListNode(2);ListNode* pNode5 = CreateListNode(4);ListNode* pNode6 = CreateListNode(1);ConnectListNode(pNode1,pNode2);ConnectListNode(pNode2,pNode3);ConnectListNode(pNode3,pNode4);ConnectListNode(pNode4,pNode5);ConnectListNode(pNode5,pNode6);ListNode* pReverseHead = Test(pNode1);DestroyList(pReverseHead);
}void Test2(){ListNode* pNode1 = CreateListNode(1);ListNode* pReverseHead = Test(pNode1);DestroyList(pReverseHead);
}void Test3(){Test(NULL);
}int main(int argc, char** argv){Test1();Test2();Test3();return 0;
}




更多相关：

  • 剑指offer：面试题22. 链表中倒数第k个节点

    题目：链表中倒数第k个节点 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。 示例： 给定一个链表: 1->2->3->4->5, 和 k =...

  • 剑指offer：面试题06. 从尾到头打印链表

    题目：从尾到头打印链表 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。 示例 1： 输入：head = [1,3,2] 输出：[2,3,1] 限制： 0 <= 链表长度 <= 10000 题目： /*** Definition for singly-linked list.* struct Lis...

  • 【力扣网练习题】合并两个有序链表

    将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。  示例：输入：1->2->4, 1->3->4 输出：1->1->2->3->4->4 解法一：双指针法 时间复杂度：O(a+b) 循环比较两个子问题的次数为 a+b a,b为两个子问题的长度空间复杂度：O(1) 双指针，常数级别复杂度...

  • 删除单链表中的重复节点(c语言版本)

    这是一道经典的面试题，下面是我的研究和举一反三，特整理如下： 分为三种情形: （1）删除有序链表的重复节点，重复节点一个都不留 （2）删除有序链表的重复节点，重复节点只留一个 （3）删除无序链表的重复节点，重复节点只留一个 下面是相关节点的定义： typedef struct ListNode {int val;struc...

  • 链表类型题目需要用到的头文件list.h

    下面是后面链表相关题目中需要用到的链表结点的定义和相关操作函数，参见下面的list.h文件： 注意链表结点的定义采用cpp的定义方式，它会被cpp的文件调用。比如后面删除链表重复结点的文件del_repeated_list.cpp中的编译方式： g++ -g del_repeated_list.cpp -o del_repeate...

  • jquery判断方法是否存在_判断图中是否有环的三种方法

    0、什么是环？在图论中，环（英语：cycle）是一条只有第一个和最后一个顶点重复的非空路径。在有向图中，一个结点经过两种路线到达另一个结点，未必形成环。1、拓扑排序1.1、无向图使用拓扑排序可以判断一个无向图中是否存在环，具体步骤如下：求出图中所有结点的度。将所有度 <= 1 的结点入队。（独立结点的度为 0）当队列不空时，弹出队首元...

  • 简单的平衡二叉树

    已知一个长度为11的线性表List=(12, 24, 36, 90, 52, 30, 41, 8, 10, 38, 61)，试回答下面问题 （1）将线性表元素依次插入一个空的平衡二叉树，画出所得平衡二叉树，如果假设每个元素查找概率相同，则平均查找长度为多少？   (1) 插入12, 这是第一个结点,是根结点.   (2) 插入...

  • 有一个1亿结点的树,已知两个结点, 求它们的最低公共祖先!

    对该问题,分为如下几种情形讨论: 情形一: 假如该树为二叉树,并且是二叉搜索树, 依据二叉搜索树是排过序的, 我们只需要从树的根结点开始,逐级往下,和两个输入的结点进行比较. 如果当前结点的值比两个结点的值都大,那么最低的公共祖先一定在当前结点的左子树中,下一步遍历当前结点的左子节点. 如果当前结点的值比两个结点的值都小,那么...

  • （点）分治学习笔记

    哗我看了一下好像没有很详细专门讲分治的blog？那就主要先学一下点分治吧，其他的……等我记得把C++一本通带到机房来再说吧先咕着啦 写在前面 刷题进度 入门题（0/3） 好题(0/9) 问题解决进度 Q1 Q2  正文 淀粉质 点分治 点分治就是在一棵树上，对具有某些限定条件的途径静态地进行统计的算法。 ——《算法竞赛 进阶指南》...

  • B树，B+树，B-树和B*树

    B树        即二叉搜索树：        1.所有非叶子结点至多拥有两个儿子（Left和Right）；        2.所有结点存储一个关键字；        3.非叶子结点的左指针指向小于其关键字的子树，右指针指向大于其关键字的子树；        如：               ...

  • 剑指offer 重建二叉树 python

    题目描述 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。 样例 输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6} 返回二叉树头节点 想法： 使用递归，既然给你前序遍历序列和中序遍历序列，所以可以通过前序遍历的第一个为...

©2024 11GX.COM