怒刷力扣(删除排序链表中的重复元素)

简介: 单链表是我们在数据结构中非常常见的链表,那么最简单的删除链表元素你会吗?什么so easy?那下一篇?

删除排序链表中的重复元素

WangScaler: 一个用心创作的作者。

声明:才疏学浅,如有错误,恳请指正。

题目

给定一个已排序的链表的头 head删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表

初步分析

这个题会链表的话感觉就很简单没什么复杂的过程,如下图所示。当我们当前指针的指向的值2和后边的2是一样的时候,直接将当前指针下一个节点指向下下个数3,即直接丢弃中间这个重复的值2。那么下一次比较的时候,当前值2,如果和后边的数3不一样,则当前的值往后移动为3,如果一样,则重复上一次的操作。

image.png

继续分析

那么剩下来的就是怎么遍历链表的问题了。首先得回到首节点,必须引入一个新的链表,指向这个链表。那么就拿到之前链表的头节点,这时候如果他的next节点不为空,就继续遍历。

答案

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public ListNode deleteDuplicates(ListNode head) {
    if (head == null) {
        return head;
    }
​
    ListNode cur = head;
    while (cur.next != null) {
        if (cur.val == cur.next.val) {
            cur.next = cur.next.next;
        } else {
            cur = cur.next;
        }
    }
​
    return head;
}

复杂度

  • 时间复杂度: O(n),需要遍历一遍链表。
  • 空间复杂度:O(1)。

总结

单链表是我们在数据结构中非常常见的链表,那么最简单的删除链表元素你会吗?什么so easy?那下一篇?你不会?我这里随便在网上找了篇文章,不会链表的可以去看看。图解!链表真的很简单

这个题关键就是指针指向问题以及怎么寻找头指针以及怎么遍历链表。链表分为数据域和指针域,比较数据域,修改指针域。

删除链表的元素是链表的基本操作,我感觉这个题,可能是为后续的题做的铺垫,那么我们拭目以待吧。

都来了,点个赞再走呗!

关注WangScaler,祝你升职、加薪、不提桶!

目录
相关文章
|
5月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
56 1
|
5月前
【LeetCode 27】347.前k个高频元素
【LeetCode 27】347.前k个高频元素
59 0
|
5月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
40 4
|
5月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
44 0
Leetcode第三十三题(搜索旋转排序数组)
|
5月前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
132 0
|
5月前
【LeetCode 06】203.移除链表元素
【LeetCode 06】203.移除链表元素
45 0
|
5月前
【LeetCode-每日一题】移除元素
【LeetCode-每日一题】移除元素
44 0
|
6月前
|
Unix Shell Linux
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
本文提供了几个Linux shell脚本编程问题的解决方案,包括转置文件内容、统计词频、验证有效电话号码和提取文件的第十行,每个问题都给出了至少一种实现方法。
LeetCode刷题 Shell编程四则 | 194. 转置文件 192. 统计词频 193. 有效电话号码 195. 第十行
|
7月前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法,用于按照之字形顺序打印二叉树的层次遍历结果,实现了在奇数层正序、偶数层反序打印节点的功能。
81 6
|
7月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
165 2