寒光博客

[java] 单链表实战 删除重复节点
题目 移除未排序链表中的重复节点 进阶: 不得使用临时缓冲区 怎么解决 思路: 缓冲区 hashset 重复判...
扫描右侧二维码阅读全文
12
2019/10

[java] 单链表实战 删除重复节点

题目

移除未排序链表中的重复节点

  • 进阶:
    不得使用临时缓冲区 怎么解决

思路:
缓冲区 hashset 重复判断 然后删除

缓冲区 代码

package _09_Linear;

import java.util.HashSet;

public class RemoveRepeitionNode {
    private static class Node {
        Object value;
        Node next;

        public Node(Object value) {
            this.value = value;
        }
    }

    public static void main(String[] args) {
        int arr[] = {1, 6, 4, 2, 7, 6, 8, 1};
        Node head = new Node(null);//哑元
        Node p = head;
        for (int i = 0; i < arr.length; i++) {
            p.next = new Node(arr[i]);
            p = p.next;
        }
        rr(head);//有缓冲区
//        rr2(head);//无缓冲区
        Node p1 = head.next;
        while (p1 != null) {
            System.out.println(p1.value);
            p1 = p1.next;
        }

    }

    /**
     * 使用缓冲区
     *
     * @param head
     */
    private static void rr(Node head) {
        HashSet set = new HashSet();//开辟新空间
        Node p1 = head.next;
        Node pre = head;
        while (p1 != null) {
            if (set.contains(p1.value)) {//重复
                System.out.println("delete:" + p1.value);
                pre.next = p1.next;//删除
            } else {
                set.add(p1.value);//加入队列
                pre = p1;//更新前驱pre 很重要!!! 注意理解
            }

            p1 = p1.next;
        }
    }
}

非缓冲区

建立一个哨兵 然后依次后移哨兵
每个哨兵对其后面的所有元素进行一轮比较 查重复 删除

    /**
     * 无缓冲区 删除重复节点
     * 使用哨兵 检测 重复
     *
     * @param head
     */
    private static void rr2(Node head) {
        Node pre = head;
        Node p = pre.next;
        while (p != null) {
            Node sentry = p;//哨兵 并保持不变
            while (p.next != null) {//从哨兵之后开始比较
                if (sentry.value == p.next.value) {// 重复
                    p.next = p.next.next;
                } else {
                    p = p.next;
                }
            }
            p = pre;//恢复p
            p = p.next;//p后移
            pre = p;//保存p
        }
        System.out.println(":asdasd");

    }

tip:删除重复节点的两种方法

本文作者:Author:     文章标题:[java] 单链表实战 删除重复节点
本文地址:https://dxoca.cn/java/290.html       百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
Last modification:October 13th, 2019 at 10:10 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment