leetcode算法83.删除排序链表中的重复元素

简介: 本文讲解如何用leetcode算法83.删除排序链表中的重复元素。

一、leetcode算法



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


1.1、题目


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


示例 1:


输入:head = [1,1,2]

输出:[1,2]

示例 2:


输入:head = [1,1,2,3,3]

输出:[1,2,3]


1.2、思路


思路一:由于链表是排序好的,那么我们只需要从第一个开始,让他们两个之间相互比较,假如第一个和第二个相等,那么就把第一个节点的next指向第三个节点的位置,这样重复的第二个就被删掉了,直到遍历完整个链表。


1.3、答案


19.png


class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null){
            return head;
        }
        //定义一个游标,用来判断链表是否遍历完
        ListNode pre = head;
        //判断游标下一个是否还有,如果没有证明链表遍历完毕
        while(pre.next != null){
            //判断当前节点的值和下一个节点的值是否相等
            if(pre.val == pre.next.val ){
                //如果相等则将当前值的下一个指向,指向当前节点的下下一个,也就是说如果原来当前节点1指向2,2指向3,
                //那么现在1直接指向3,把中间的2去掉,因为2和1的值是相等的
                pre.next = pre.next.next;
            }else{
                //如果不相等,则将pre指向下一个节点。
                pre = pre.next;
            }
        }
        return head;
    }
}


复杂度分析


时间复杂度:O(n),其中 n 是链表的长度。


空间复杂度:O(1)。

相关文章
|
3月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
46 1
|
3月前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
60 0
Leetcode第21题(合并两个有序链表)
|
2月前
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
|
3月前
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
40 2
|
3月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
30 0
Leetcode第三十三题(搜索旋转排序数组)
|
3月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
34 0
LeetCode第二十四题(两两交换链表中的节点)
|
3月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
50 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
3月前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
112 0
|
3月前
【LeetCode 10】142. 环形链表 II
【LeetCode 10】142. 环形链表 II
30 0
|
3月前
【LeetCode 09】19 删除链表的倒数第 N 个结点
【LeetCode 09】19 删除链表的倒数第 N 个结点
22 0