专栏首页一点博客LeetCode:移除重复节点-java实现

LeetCode:移除重复节点-java实现

题目描述

编写代码,移除未排序链表中的重复节点。保留最开始出现的节点。

示例1:

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

输出:[1, 2, 3]

示例2:

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

输出:[1, 2]

提示:

链表长度在[0, 20000]范围内。

链表元素在[0, 20000]范围内。

实现代码

package com.chenbin.demo;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Set;

public class Day0626 {
public static ListNode removeDuplicateNodes(ListNode head) {

if (head == null || head.next == null) {
return head;
        }
        Set<Integer> set = new HashSet<>();
        ListNode p = head;
set.add(p.val);
while (p.next != null ) {
if (set.contains(p.next.val)) {
                p.next = p.next.next;
            }else {
set.add(p.next.val);
                p = p.next;
            }
        }
return head;
    }

public static int[] stringToIntegerArray(String input) {
        input = input.trim();
        input = input.substring(1, input.length() - 1);
if (input.length() == 0) {
return new int[0];
        }

        String[] parts = input.split(",");
int[] output = new int[parts.length];
for (int index = 0; index < parts.length; index++) {
            String part = parts[index].trim();
            output[index] = Integer.parseInt(part);
        }
return output;
    }

public static ListNode stringToListNode(String input) {
// Generate array from the input
int[] nodeValues = stringToIntegerArray(input);

// Now convert that list into linked list
        ListNode dummyRoot = new ListNode(0);
        ListNode ptr = dummyRoot;
for (int item : nodeValues) {
            ptr.next = new ListNode(item);
            ptr = ptr.next;
        }
return dummyRoot.next;
    }

public static String listNodeToString(ListNode node) {
if (node == null) {
return "[]";
        }

        String result = "";
while (node != null) {
            result += Integer.toString(node.val) + ", ";
            node = node.next;
        }
return "[" + result.substring(0, result.length() - 2) + "]";
    }

public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String line;
while ((line = in.readLine()) != null) {
            ListNode head = stringToListNode(line);

            ListNode ret = removeDuplicateNodes(head);

            String out = listNodeToString(ret);

            System.out.print(out);
        }
    }

}

class ListNode {
int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

解题思路:

关键词:单链表、java对象赋值和引用、链表删除节点。

整体思路:创建一个HashSet实例,从头节点开始遍历所有节点,遍历过程中如果HashSet中包括该节点的值,则判断下一个节点的值,否则将该节点的值添加到HashSet中。

明确5点:1 :每个节点都是一个对象,有不同的地址。

2:每个对象之间由next连接。

3:已知头结点,head。

4:将HashSet中已存在的节点删除(p.next = p.next.next)

5: 返回新的头结点。

实现思路:单链表好比5个单向连接的有色球,颜色有重复,人工要实现这些球颜色不重复,那么从第二个球开始判断,如果和第一个颜色一样,则将第一个球的链子连接到第三个,在从第三个的下一个判断是否重复,以此类推。人工去重的这只“手”就好比程序中对象地址的引用,因此需要实例化一个ListNode p = head;(p在遍历过程中逐一引用节点地址,若节点的值在set中已存在,则修改该节点的next)【判断值从第二个节点开始,修改节点的next从第一个节点开始】。从第一个节点开始所有节点的next都已判断校正过。包括第一个节点。而第一个节点就是head, 因此返回head即可。

核心点是ListNode p = head; p的角色和作用。

参考:java对象的引用以及对象的赋值https://blog.csdn.net/smilelvcha/article/details/81531184

本文分享自微信公众号 - 一点博客(xiaochen_182),作者:一点博客

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-06-26

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Linux-免费开源的操作系统

    Linux是一套免费使用和自由传播的类Unix操作系统,是一个基于POSIX和UNIX的多用户、多任务、支持多线程和多CPU的操作系统。它能运行...

    一点博客
  • Spark-计算引擎

    Apache Spark 是专为大规模数据处理而设计的快速通用的计算引擎。Spark是UC Berkeley AMP lab (加州大学伯克利分...

    一点博客
  • 别“狂吹”5G了!

    “5G实际上被夸大了它的作用,也被更多人夸大了华为公司的成就……实际上现在人类社会对5G还没有这么迫切的需要……不要把5G想象成海浪一样,浪潮来了,财富来了,赶...

    一点博客
  • Leetcode 141 Linked List Cycle

    Given a linked list, determine if it has a cycle in it. Follow up: Can you so...

    triplebee
  • LeetCode - 两两交换链表中的节点

    该题是第24题,这题一开始我还想了好一会儿,后来发现,好像这样子就好了。递归真的是能用就用,实在是因为递归写起来简单啊。

    晓痴
  • LeetCode 142:环形链表 II Linked List Cycle II

    为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

    爱写bug
  • LeetCode 142:环形链表 II Linked List Cycle II

    为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。如果 pos 是 -1,则在该链表中没有环。

    爱写bug
  • 解密隐藏JPEG图像中的数据

    我只会解释这个hexdump解释相关的部分。这里只有几个重要的字节来实现我们在这篇博客文章中试图做的事情。

    半月弧
  • Gin框架系列03:换个姿势理解中间件

    中间件,英译middleware,顾名思义,放在中间的物件,那么放在谁中间呢?本来,客户端可以直接请求到服务端接口。

    平也
  • 判断一个链表是否为回文结构

    题目:给定一个链表的头节点head, 请判断该链表是否为回文结构。 例如: 1->2->1, 返回true。 1->2->2->1, 返回true。

    大学里的混子

扫码关注云+社区

领取腾讯云代金券