题解 | #牛群排列去重#

牛群排列去重

https://www.nowcoder.com/practice/8cabda340ac6461984ef9a1ad66915e4?tpId=354&tqId=10591390&ru=/exam/oj/ta&qru=/ta/interview-202-top/question-ranking&sourceUrl=%2Fexam%2Foj%2Fta%3FtpId%3D354

一、知识点:

HashSet、链表

二、文字分析:

算法的实现思路如下:

  1. 如果链表为空或只有一个节点,直接返回原链表。
  2. 创建一个HashSet集合seen,用于存储已经出现过的元素值。
  3. 将链表头结点的值添加到seen中。
  4. 初始化两个指针prevcurr,分别指向当前节点和下一个节点。
  5. 使用循环遍历链表,直到当前节点curr为null。
  6. 在每一次循环中,先判断curr节点的值是否已经出现过,如果是,则说明是重复节点,删除它。将prev节点的next指针指向curr节点的下一个节点。
  7. 如果curr节点的值没有出现过,将其添加到seen集合中,并更新prev节点为curr节点。
  8. curr指针移动到下一个节点。
  9. 返回更新后的链表头结点head

该算法使用了HashSet集合来判断链表中的元素是否重复,从而删除重复节点。时间复杂度为O(n),其中n是链表的长度,需要遍历整个链表。空间复杂度为O(n),因为需要使用HashSet集合存储已经出现过的元素值,最坏情况下需要存储所有节点的值。

三、编程语言:

java

四、正确代码:

import java.util.HashSet;

public class Solution {


    public ListNode deleteDuplicates(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 创建一个集合用于存储已经出现过的编号
        HashSet<Integer> seen = new HashSet<>();
        seen.add(head.val);

        ListNode prev = head;
        ListNode curr = head.next;

        while (curr != null) {
            if (seen.contains(curr.val)) {
                // 删除重复节点
                prev.next = curr.next;
            } else {
                // 将新的编号添加到集合中
                seen.add(curr.val);
                prev = curr;
            }
            curr = curr.next;
        }

        return head;
    }
}

全部评论

相关推荐

学java时间比较短不到三个月,基本的技术栈都过了一遍就是都不太深,有个小项目。是继续找实习还是沉淀准备秋招呢?找实习的话会花很多时间在八股,放弃的话又怕秋招简历太难看。有无大佬支招
今天java了吗:1.一定要找实习,实习不一定要去,但是找实习过程中的面试经验和心态经验才是最重要的 2.八股本来就是大头,甚至比项目重要 3.这个时间段也是面试比较多的阶段,可以抓住机会锻炼。面试才会发现自己的不足,感觉自己会了和能给面试官娓娓道来是两码事
点赞 评论 收藏
分享
程序员牛肉:主要是因为小厂的资金本来就很吃紧,所以更喜欢有实习经历的同学。来了就能上手。 而大厂因为钱多,实习生一天三四百的就不算事。所以愿意培养你,在面试的时候也就不在乎你有没有实习(除非是同级别大厂的实习。) 按照你的简历来看,同质化太严重了。项目也很烂大街。 要么换项目,要么考研。 你现在选择工作的话,前景不是很好了。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务