首页 / 算法 / 每日算法题 | 剑指offer 链表专题（8）删除链表中重复的结点

每日算法题 | 剑指offer 链表专题（8）删除链表中重复的结点

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了每日算法题 | 剑指offer 链表专题（8）删除链表中重复的结点，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5078字，纯文字阅读大概需要8分钟。

内容图文

重磅干货，第一时间送达

每日算法题 | 剑指offer 链表专题（8）删除链表中重复的结点 - 文章图片

题目

删除链表中重复的结点

题目要求

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

解题思路

一开始觉得哇这题目好简单，不过是找到需要删除的节点，然后跳过该节点就行了。
思路A：新建一个哈希表，由于链表是有序的，将所有的元素出现次数记录下来，然后再开辟个链表还原现场。
我们采用最容易想到的方法，不用考虑时间效率与空间效率问题，就直接用遍历，用一个哈希表结构来记录每个节点对应的值在节点中出现了几次，统计完成后，然后通过哈希表中如果出现次数为大于等于2，再用两个指针一个前一个后开始找对应的值就行了，如果后一个指针指向的节点的值为哈希表中出现次数大于等于2的数，那么前一个指针指向后一个指针的next然后删除后一个指针所指向的节点，让后一个指针重新指向前一个指针的next，就这样就可以完成删除。

虽然这个方法可以，但是时间复杂度为O(N)， 空间复杂度为一个哈希表的结构，所以采用这种不是最佳选择。

哈希表O（N），链表也是O（N），时间复杂度O（N）

思路B：思路A当然是暴力解法，要是空间有限制那就不行了。既然是链表结构，我们就要学会巧用指针，一个指针不能满足需求那就用两个指针，这样空间复杂度可以降到最小，时间复杂度即便是O（N+M）也可以约等于O（N）

首先添加一个头节点，以方便碰到第一个，第二个节点就相同的情况

2.设置pre ，last指针， pre指针指向当前确定不重复的那个节点，而last指针相当于工作指针，一直往后面搜索。

也就是说只有当last指针确定了这个元素只出现一次，pre接上，如果这个元素出现多次，last请你遍历到下一个元素重新开始判断出现的次数。

可能出现的情况：

（1）1->1 [从第一个元素开始到最后一个元素都是同一个元素]

(2) 1->2->2 [第一个元素保留后面的元素为同一元素]

(3) 1->2->2->3 [第一个元素保留后面的元素为同一元素最后一个元素不重复]

(4) 1 [只有一个元素]

(5) 1->1->2->2->3->3 [所有出现的元素个数都超过了1]

每日算法题 | 剑指offer 链表专题（8）删除链表中重复的结点 - 文章图片

这道题目在牛客网上的通过率还不到20％，还是比较难AC的一道题目!

代码实现

Python :

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def deleteDuplication(self, pHead):
        # write code here
        if not pHead or pHead.next==None:
            return pHead
        Head=ListNode(0)
        Head.next=pHead
        pre=Head
        last=pHead
        while last!=None:
            if last.next!=None and last.val == last.next.val   :
                while last.next!=None and last.val==last.next.val :
                    last=last.next
                pre.next=last.next
                last=last.next
            else:
                pre=pre.next
                last=last.next
        return Head.next

JAVA

if (pHead==null || pHead.next==null){return pHead;}
ListNode Head = new ListNode(0);
Head.next = pHead;
ListNode pre  = Head;
ListNode last = Head.next;
while (last!=null){
    if(last.next!=null && last.val == last.next.val){
        // 找到最后的一个相同节点
        while (last.next!=null && last.val == last.next.val){
            last = last.next;
        }
        pre.next = last.next;
        last = last.next;
    }else{
        pre = pre.next;
        last = last.next;
    }
}
return Head.next;

后记

注：面试季来了，不管是作为面试者还是以后作为面试官，了解算法这门程序员之间的沟通方式都是非常必要的。找过工作的朋友应该都听说过《剑指offer》，虽然书中只有六十多道题目，但是道道都是经典。

如果是单纯的面试需求，剑指offer的优先级肯定是在Leetcode之前，总的说它有三个优点：

1.很可能在面试中出现原题
2.约66题，题量少，但是涵盖的内容较全
3.能培养一个良好的刷题习惯

它的缺点是：

1.只有66题，刷着容易过拟合
2.动态规划的题比较少，因此需要在Leetcode上专项训练。
算法题主要分成数据结构和具体算法部分，简单归类如下。基本每道题都很精彩，所以这里就不一一洗写了，题解可以看看我的代码仓库或者讨论区的内容。

以下是剑指offer题目，蓝色为已发布连接。

数据结构类题目
LinkedList
003-从尾到头打印链表
014-链表中倒数第k个结点
015-反转链表
016-合并两个或k个有序链表
025-复杂链表的复制
036-两个链表的第一个公共结点
055-链表中环的入口结点
056-删除链表中重复的结点
Tree
004-重建二叉树
017-树的子结构
018-二叉树的镜像
022-从上往下打印二叉树
023-二叉搜索树的后序遍历序列
024-二叉树中和为某一值的路径
026-二叉搜索树与双向链表
038-二叉树的深度
039-平衡二叉树
057-二叉树的下一个结点
058-对称的二叉树
059-按之字形顺序打印二叉树
060-把二叉树打印成多行
061-序列化二叉树
062-二叉搜索树的第k个结点
Stack & Queue
005-用两个栈实现队列
020-包含min函数的栈
021-栈的压入、弹出序列
044-翻转单词顺序列(栈)
064-滑动窗口的最大值(双端队列)
Heap
029-最小的K个数
Hash Table
034-第一个只出现一次的字符
图
065-矩阵中的路径(BFS)
066-机器人的运动范围(DFS)
具体算法类题目
斐波那契数列
007-斐波拉契数列
008-跳台阶
009-变态跳台阶
010-矩形覆盖
搜索算法
001-二维数组查找
006-旋转数组的最小数字（二分查找）
037-数字在排序数组中出现的次数（二分查找）
全排列
027-字符串的排列
动态规划
030-连续子数组的最大和
052-正则表达式匹配(我用的暴力)
回溯
065-矩阵中的路径(BFS)
066-机器人的运动范围(DFS)
排序
035-数组中的逆序对(归并排序)
029-最小的K个数(堆排序)
029-最小的K个数(快速排序)
位运算
011-二进制中1的个数
012-数值的整数次方
040-数组中只出现一次的数字
其他算法
002-替换空格
013-调整数组顺序使奇数位于偶数前面
028-数组中出现次数超过一半的数字
031-整数中1出现的次数（从1到n整数中1出现的次数）
032-把数组排成最小的数
033-丑数
041-和为S的连续正数序列(滑动窗口思想)
042-和为S的两个数字(双指针思想)
043-左旋转字符串(矩阵翻转)
046-孩子们的游戏-圆圈中最后剩下的数(约瑟夫环)
051-构建乘积数组

剑指offer刷题交流群

扫码添加微信，一定要备注研究方向+地点+学校+昵称（如机器学习+上海+上交+汤姆），只有备注正确才可以加群噢。

每日算法题 | 剑指offer 链表专题（8）删除链表中重复的结点 - 文章图片
▲长按加群

每日算法题 | 剑指offer 链表专题（8）删除链表中重复的结点 - 文章图片

内容总结

以上是互联网集市为您收集整理的每日算法题 | 剑指offer 链表专题（8）删除链表中重复的结点全部内容，希望文章能够帮你解决每日算法题 | 剑指offer 链表专题（8）删除链表中重复的结点所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/616614.html

来源：【匿名】

【上一篇】每日算法题 | 剑指offer 链表专题（9）合并两个有序链表【下一篇】浅谈php实现映射的两种方法（链表和二叉树）

更多 ►

【每日算法题 | 剑指offer 链表专题（8）删除链表中重复的结点】教程文章相关的互联网学习教程文章

九章算法面试题28 链表找环

九章算法官网-原文网址http://www.jiuzhang.com/problem/28/题目初阶：给一个单链表，判断这个单链表是否存在环，如1->2->3->4->2是一个存在环的链表。要求使用O(1)的额外空间。进阶：求出环的入口。同样要求O(1)的额外空间。解答初阶：用两根指针，从链表头出发，一根慢指针每次走一步，另外一根快指针每次走两步。直到他们相遇（有环）或者快指针走到NULL（无环）。进阶：相遇之后，将一根指针挪到链表头，两根指针每次都移动一步...

【数据结构与算法】java链表操作

链表操作代码量少但是比较容易出错，是比较适合面试的地方。代码实现/*** 源码名称：MyLinkList.java * 日期：2014-09-05* 程序功能：java链表操作 * 版权：CopyRight@A2BGeek * 作者：A2BGeek*/ import java.util.Stack;public class MyLinkList {class LinkNode<T> {private T mValue;private LinkNode<T> mNext;public LinkNode(T value) {// TODO Auto-generated constructor stubmValue = value;}public void setValue(T valu...

数据结构与算法分析 3.4&3.5 — 链表的交与并算法【代码】【图】

代码： #include <list>template<typename ElementType> list<ElementType> Intersect(const list<ElementType> &list_1, const list<ElementType> &list_2) {list<ElementType> result;auto leftPos = list_1.begin( );auto rightPos = list_2.begin( );while (leftPos != list_1.end() && rightPos != list_2.end()){if (*leftPos > *rightPos)rightPos++;elseif (*leftPos < *rightPos)leftPos++;else{result.push_back(*leftPo...

python数据结构与算法第七天【链表】【图】

1.链表的定义如图：注意：（1）线性表包括顺序表和链表（2）顺序表是将元素顺序地存放在一块连续的存储区里（3）链表是将元素存放在通过链构造的存储快中原文：https://www.cnblogs.com/liuzhiqaingxyz/p/9439814.html

算法题——翻转链表中的一段【代码】

题目：给出一个链表中的两个指针p1和p2，将其之间的结点翻转。思路：可以通过交换结点内的值来实现结点的翻转，空间为O(N)；如果要求不能交换值，那么仅凭p1和p2是无法翻转的，只能交换两个指针之间的链表。代码：交换值： 1struct ListNode 2{3int val;4 ListNode *next;5};6 7void reverseNodes(ListNode *p1, ListNode *p2) {8if ( p1 == NULL || p2 == NULL ) 9return; 1011 vector<ListNode*> nodes; 12for(vector<...

算法提高——链表练习2【图】

链表练习2PAT乙级1025/甲级1074：反转链表算法思路：将链表分块，每k个节点一块，针对每块中的节点进行反转操作反转链表的伪代码　　设该区域头节点为head，定义指针p，q，r　　p=head;　　q=p->next　　p->next = null;　　while(k--){　　　　r = q->next;　　　　q->next = p->next;　　　　p->next = q;　　　　q = r; 　　}循环结束r指向下一组的开头，所以可以返回r作下一组的头指针　　然后可以采用递归实现算法，需要注...

算法-创建链表【代码】【图】

掌握数据结构和算法，尤其是链表，面试编程题经常考下面是用尾插法创建链表#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include<malloc.h> #include <string.h>typedef struct node {int data;struct node *next; }Node;Node *LinkListCreat(int n)//链表创建函数{Node *p;Node *head,*rear;int i = 0; Node *Tal;head = (Node *)malloc(sizeof(Node));rear = head;rear->next = NULL;for (i = 0; i < n; i++){p = (Nod...

链表万历算法

# include <stdio.h># include <malloc.h># include <stdlib.h> typedef struct Node{ int data; //数据域 struct Node *pNext;//指针域 } NODE, *PNODE; //NODE 等价于 struct Node PNODE等价于 struct Node * //函数声明 PNODE create_list(void); void traverse_list(PNODE pHead); int main(void) { PNODE pHead =NULL;// 等价于struct PNODE * pHead=NULL pHead=create_list(); //创建一个非循环单链表，并将该链表...

008实现一个算法从一个单链表中返回倒数第n个元素（keep it up）

我们维护两个指针，它们之间的距离为n。然后。我将这两个指针同步地在这个单链表上移动，保持它们的距离为n不变。那么，当第二个指针指到空时。第一个指针即为所求。#include <iostream>struct Node {int data;Node* next; };void initList(Node* vNode) {for (int i=0; i < 20; ++i){Node* TempNode = new Node;TempNode->data = i;TempNode->next = vNode->next;vNode->next = TempNode;} }Node* getNthBackWards(const N...

算法复习：链表【代码】

链表必须清楚掌握链表定义struct ListNode {int val;ListNode *next; };创建链表头ListNode* creat()//创建头{struct ListNode *node=(struct ListNode *)malloc(sizeof(struct ListNode));node->next=NULL;return node; }创建一个新节点（插入时调用）ListNode* make_node(int num)//建新节点{struct ListNode *node=(struct ListNode *)malloc(sizeof(struct ListNode));node->val=num;node->next=NULL;return node; }插入新节点...

算法面试3---链表【代码】【图】

1 链表反转例1：LeetCode 206。本题虽然简单但却是众多公司的面试问题。反转前后的图示如下：在反转的过程中主要是依据指针之间的移动，如下图所示：class Solution {public ListNode reverseList(ListNode head) {ListNode prev = null;while (head != null) {//1 每次修改前先把head.next备份否则head修改后找不到head.nextListNode nextTemp = head.next; //2 修改head.next temp用来保存的是上次头节点的信息head.next = prev...

算法总结之两个链表生成相加链表【代码】

假设链表中每一个节点的值都在0~9之间，那么链表整体就可以代表一个整数给定两个链表的头节点head1和head2,请生成代表两个整数相加值的结果链表传统做法先把链表生成整数然后相加这样的有个溢出问题介绍一种做法：利用栈结构求解： 1、将两个链表分别从左到右遍历，遍历过程中将值压栈，这样就生成了两个链表节点的逆序栈s1 和 s2。2、将s1和s2同步弹出，这样相当于两个链表从低位到高位一次弹出，在这个过程中生成相加链表...

数据结构-单向链表相关算法

#include <stdio.h>#include <stdlib.h>#define OVERFLOW -2#define OK 1#define ERROR 0typedef int ElemType;//单向链表结构体typedef struct LNode { ElemType data; struct LNode *next;}LNode,*LinkList;LinkList CreateList_L(LinkList L,int n);void TraverseList_L(LinkList L);int GetElem_L(LinkList L,int i,ElemType *e);LinkList ListInsert_L(LinkList L,int i,ElemType e);LinkList ListDelete(LinkList L,in...

二叉树（一）——二叉树的基本实现（数组实现和链表实现）【图】

1.树是一种数据结构，树的一些相关的术语：结点的度：一个结点的后继结点的个数。树的度：树中度值最大的结点的度被称为树的度。树的深度：树的层次数。分支结点：度值大于0的结点，分支结点至少含有一个后继，分支结点也称为非终端结点。叶子结点：树中的度值为0的结点。双亲结点：树中某个结点的前驱结点，也成为父节点。子女结点：树中某结点的后继结点。兄弟结点：树中同一层的结点。 2.二叉树（1）二叉树是一种特殊的...

算法之有序链表和平衡二叉树

题目描述：Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.给定一个有序的链表，要求构建一颗平衡二叉查找树。解析：二叉查找树的中序遍历的结构就是一颗二叉查找树，要使得最终的二叉查找树的结构尽可能的平衡，也就是说只需要将左右两边的节点数尽可能的均匀，(注意，此处的均匀是一个递归的概念，也就是说每一个节点的左右子树的节点个数都应该尽量均匀)。我们...

链表 - 相关标签

链表c语言链表排序

算法 - 最热教程

浅谈SQLServer查询优化器中的JOIN算法有没那种可逆算法是密文比明文短的呢？...javascript-类似Excel里面的NORMDIST函...C++中的分治算法及常见题目汇总压缩感知重构算法综述-学习笔记 c++中内置函数qsort（快速排序）和bsea...一、fpga图像处理算法整合基于遗传算法（deap）的非线性函数寻优...集成学习-Bagging集成学习算法随机森林...机器学习笔记（九）聚类算法及实践（K-...

首页 / 算法 / 每日算法题 | 剑指offer 链表专题 （8） 删除链表中重复的结点

每日算法题 | 剑指offer 链表专题 （8） 删除链表中重复的结点

内容导读

内容图文

题目

题目要求

解题思路

也就是说只有当last指针确定了这个元素只出现一次，pre接上，如果这个元素出现多次，last请你遍历到下一个元素重新开始判断出现的次数。

可能出现的情况：

（1）1->1 [从第一个元素开始到最后一个元素都是同一个元素]

(2) 1->2->2 [第一个元素保留 后面的元素为同一元素]

(3) 1->2->2->3 [第一个元素保留 后面的元素为同一元素 最后一个元素不重复]

(4) 1 [只有一个元素]

(5) 1->1->2->2->3->3 [所有出现的元素个数都超过了1]

这道题目在牛客网上的通过率还不到20％，还是比较难AC的一道题目!

代码实现

Python :

JAVA

后记

数据结构类题目

内容总结

内容备注

内容手机端

【每日算法题 | 剑指offer 链表专题 （8） 删除链表中重复的结点】教程文章相关的互联网学习教程文章

算法 - 相关标签

链表 - 相关标签

算法 - 最新教程

算法 - 最热教程

首页 / 算法 / 每日算法题 | 剑指offer 链表专题（8）删除链表中重复的结点

每日算法题 | 剑指offer 链表专题（8）删除链表中重复的结点

(2) 1->2->2 [第一个元素保留后面的元素为同一元素]

(3) 1->2->2->3 [第一个元素保留后面的元素为同一元素最后一个元素不重复]

【每日算法题 | 剑指offer 链表专题（8）删除链表中重复的结点】教程文章相关的互联网学习教程文章