LeetCode – 面试题02.01.移除重复点 – Java – 细喔

题目

在这里插入图片描述


题目解析

不知道大家是否注意到 我划线的部分。
该链表处于未排序的状态,要求在此状态下,删除重复节点。
难点: 不想前面我们做过的题,那个链表是排过序的。 两个重复的节点一定是紧挨在一起。
而现在是分离的!也就是说不能使用前面那种方法:找到两个val值相同的节点,直接用 前面 的节点 next 来覆盖后面节点的next,依次来达到删除重复节点,还剩余前面节点的目的。
在这里插入图片描述


解题思维 - 利用双重循环来解决问题。

单向链表删除节点的方式,是改变不了的。
删除重复节点,还留这"前驱节点",还是需要利用 前驱节点 的 next 来 覆盖 当前节点。
难点就在这!


第一步: 创建一个 head 的 替身 cur1,再创建一个 cur1 的替身cur2

在这里插入图片描述


我的思维是 cur1 用来标记当前某个节点。而cur2则用来 寻找 与 cur1.val 相同的节点。

处理方式如下:
在这里插入图片描述


 

附上代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeDuplicateNodes(ListNode head) {
        if(head == null){
            return head;
        }
        ListNode cur1 = head;
        while(cur1 != null){
            ListNode cur2 = cur1;
            while(cur2.next!=null){
                if(cur2.next.val == cur1.val){
                    cur2.next =cur2.next.next;
                }else{
                    cur2 =cur2.next;
                }
            }
            cur1 =cur1.next;
        }
        return head;
    }
}

在这里插入图片描述


最后,其实还有一种 解法,利用HashSet,但是作者还没有学到hash表。我就直接摘取 力扣上的了,懂得人可以自己琢磨一下。

在这里插入图片描述
不过作者还是能知道代码的大概意思的。
删除原理 与 我们上一种解法是一样的。
在这里插入图片描述


最后附上这题代码(虽然作者还没有学,但是看懂了,就根据自己的理解将代码写出来了)

class Solution {
    public ListNode removeDuplicateNodes(ListNode head) {
        if(head == null){
            return head;
        }
        Set<Integer> occurred = new HashSet<>();
        occurred.add(head.val);
        ListNode pos = head;
        while(pos.next!=null){
            ListNode cur = pos.next;// 这个 cur 永远都是等于 pos.next
            if(occurred.add(cur.val)){
                pos =  pos.next;
            }else{
                pos.next =pos.next.next;
            }
        }
        return head;
    }
}

在这里插入图片描述

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇

)">
下一篇>>