链表--如何从链表中删除重复数据

怼烎@ 2022-01-23 12:45 410阅读 0赞

### 方法一 ###

思路：遍历链表，将链表中的数据存储到HashTable中，若当前遍历的数据在HashTable中存在，说明这个数据重复，可以将这个数据删除掉。  
优点：时间复杂度较低。  
缺点：空间复杂度高，要申请额外的空间。

/**
         * 遍历链表，将链表中的数据存储到HashTable中，若当前遍历的数据在HashTable中存在，说明这个数据重复，可以将这个数据删除掉
         * @param head
         */
        public void deleteDuplecate(Node head){
            if (null == head){
                System.out.println("链表为空");
                return;
            }
            Hashtable<Integer,Integer> table = new Hashtable<Integer, Integer>();
            Node tmp = head;
            Node pre = null;
            while (tmp != null){
                //当前访问的值，在hashtable中存在
                if (table.containsKey(tmp.data)){
                    //若当前遍历的数据在HashTable中存在，说明这个数据重复，可以将这个数据删除掉
                    pre.next = tmp.next;
                    size--;
                }else{//不包含此值,把这个键值对插入
                    table.put(tmp.data,1);
                    pre = tmp;
                }
                tmp = tmp.next;
            }
        }

### 方法二 ###

思路：对链表进行双重循环遍历，外层循环正常遍历链表，若当前遍历到的结点为curNode，内层循环从curNode.next开始遍历，若碰到与curNode结点的值相同的结点，删除掉这个重复的结点。

/**
         * 对链表进行双重循环遍历，
         * 外层循环正常遍历链表，若当前遍历到的结点为curNode
         * 内层循环从curNode.next开始遍历，若碰到与curNode结点的值相同的结点，删除掉这个重复的结点
         * @param head
         */
        public void deleteDuplecate1(Node head){
            if (null == head){
                System.out.println("链表为空");
                return;
            }
            Node curNode = head;
            while (curNode != null){
                Node insideNode = curNode;
                while (insideNode.next != null){
                    if (curNode.data == insideNode.next.data){
                        insideNode.next = insideNode.next.next;
                        size--;
                    }else{
                        insideNode = insideNode.next;
                    }
                }
                curNode = curNode.next;
            }
        }

优点：空间复杂度较低，不需要申请额外的空间。  
缺点：时间复杂度较高。

package linklist;
    
    import org.junit.Test;
    
    import java.util.Hashtable;
    
    /**
     * 明白头指针与头结点的区别:
     * 头结点，放在第一个元素结点之前，其数据域一般无意义（存放链表长度）
     * 头指针：链表中指向第一个结点的指针
     * @author kankan
     * @creater 2019-06-01 7:56
     */
    public class LinkedList {
        int size;//链表节点的个数
        Node head = null;//链表头的引用
        /**
         * 头插法
         */
        public int addNodeHead(int data){
            Node newNode = new Node(data);//1.生成新结点
            if (0 == size){//2.判断是否是头结点
                head = newNode;
            }else{
                newNode.next = head;
                head = newNode;//让头指针指向第一个结点
            }
            size++;
            return data;
        }
        // 注意这里 index 从 0 开始
        public int addNodeIndex(int index,int data) {
            if (index < 0 || index > size) {
                System.out.println("角标越界！");
                return -1;
            }
            if (index == 0) {
                return addNodeHead(data);//头插法
            } else if (index == size) {
                return addNodeTail(data);//尾插法
            } else {
                Node pre = head;
                Node cur = head.next;
                //
                while (pre != null && index > 1) {
                    pre = pre.next;
                    cur = cur.next;
                    index--;
                }
                //循环结束后 pre 保存的是索引的上一个节点 而 cur 保存的是索引值当前的节点
                Node node = new Node(data);
    
                node.next = cur;
                pre.next = node;
                size++;
            }
            return data;
        }
    
        /**
         * 向链表中插入数据
         * 尾插法
         * 每次的新结点都插在终端结点的后面
         */
        public int addNodeTail(int data){
            Node newNode = new Node(data);//1.生成新结点
            if (0 == size){//2.判断头指针指向第一个是否为null
                head = newNode;
            }else{
                //3.遍历到终点
                Node tmp = head;
                while (tmp.next != null){
                    tmp = tmp.next;
                }
                tmp.next = newNode;//4.遍历到终端结点,进行插入
            }
            size++;
            return data;
        }
        //在链表头删除元素
        public boolean deleteHead(){
            if (null == head) {
                System.out.println("当前链表为空！");
                return false;
            }
            int obj = head.data;
            head = head.next;
            size--;
            return true;
        }
        /**
         * 删除第index个结点
         * 第一个结点的存储位置称为头指针
         */
        public boolean deleteNode(int index){
            if (index < 0 || index >= size){
                System.out.println("下标越界或小于0");
                return false;
            }
            //删除链表第一个元素
            if (0 == index){
                head = head.next;
                size--;
                return true;
            }
            int i = 1;
            Node pre= head;
            Node cur = pre.next;
            while (cur != null){
                if (i == index){
                    pre.next = cur.next;
                    size--;
                    return true;
                }
                pre = cur;
                cur = cur.next;
                i++;
            }
            return true;
        }
        //尾删除法
        public boolean deleteTail(){
            if (null == head) {
                System.out.println("当前链表为空！");
                return false;
            }
            if (1 == size){
                head = null;
            }else{
                Node deleteNode = head;
                //找到倒数第二个不指向null结点，因为我们删除倒数第一个结点
                while (deleteNode.next != null && deleteNode.next.next != null) {
                    deleteNode = deleteNode.next;
                }
                deleteNode.next = null;//倒数第二个结点的next赋null
            }
            size--;
            return true;
        }
        //显示节点信息
        public void display(){
            if(size > 0){
                Node node = head;
                int tempSize = size;
                if(tempSize == 1){//当前链表只有一个节点
                    System.out.println("["+node.data+"]");
                    return;
                }
                while(tempSize>0){
                    if(node.equals(head)){
                        System.out.print("["+node.data+"->");
                    }else if(node.next == null){
                        System.out.print(node.data+"]");
                    }else{
                        System.out.print(node.data+"->");
                    }
                    node = node.next;
                    tempSize--;
                }
                System.out.println();
            }else{//如果链表一个节点都没有，直接打印[]
                System.out.println("[]");
            }
        }
    
        /**
         * 选择排序
         * 返回排序后的头结点
         * @param args
         */
        public Node orderList(){
            Node nextNode = null;
            int temp = 0;
            Node curNode = head;
            while(curNode.next != null){
                nextNode = curNode.next;
                while (nextNode != null){
                    //数据从小到大
                    if (curNode.data > nextNode.data){
                        temp = curNode.data;
                        curNode.data = nextNode.data;
                        nextNode.data = temp;
                    }
                    nextNode = nextNode.next;
                }
                curNode = curNode.next;
            }
            return head;
        }
    
        //从链表中删除重复数据
    
        /**
         * 遍历链表，将链表中的数据存储到HashTable中，若当前遍历的数据在HashTable中存在，说明这个数据重复，可以将这个数据删除掉
         * @param head
         */
        public void deleteDuplecate(Node head){
            if (null == head){
                System.out.println("链表为空");
                return;
            }
            Hashtable<Integer,Integer> table = new Hashtable<Integer, Integer>();
            Node tmp = head;
            Node pre = null;
            while (tmp != null){
                //当前访问的值，在hashtable中存在
                if (table.containsKey(tmp.data)){
                    //若当前遍历的数据在HashTable中存在，说明这个数据重复，可以将这个数据删除掉
                    pre.next = tmp.next;
                    size--;
                }else{//不包含此值,把这个键值对插入
                    table.put(tmp.data,1);
                    pre = tmp;
                }
                tmp = tmp.next;
            }
        }
        //从链表中删除重复数据
    
        /**
         * 对链表进行双重循环遍历，
         * 外层循环正常遍历链表，若当前遍历到的结点为curNode
         * 内层循环从curNode.next开始遍历，若碰到与curNode结点的值相同的结点，删除掉这个重复的结点
         * @param head
         */
        public void deleteDuplecate1(Node head){
            if (null == head){
                System.out.println("链表为空");
                return;
            }
            Node curNode = head;
            while (curNode != null){
                Node insideNode = curNode;
                while (insideNode.next != null){
                    if (curNode.data == insideNode.next.data){
                        insideNode.next = insideNode.next.next;
                        size--;
                    }else{
                        insideNode = insideNode.next;
                    }
                }
                curNode = curNode.next;
            }
        }
        @Test
        public void testcase() {
            LinkedList list = new LinkedList();
            System.out.println("测试头插法");
            list.addNodeHead(1);
            list.display();
            list.addNodeHead(2);
            list.addNodeHead(3);
            list.display();
            list.addNodeTail(4);
            list.display();
            System.out.println("测试某个位置删除法");
            list.deleteNode(3);
            list.display();
            System.out.println("测试删除重复数据前");
            list.addNodeHead(1);
            list.display();
            System.out.println("测试删除重复数据");
            list.deleteDuplecate1(list.head);
            list.display();
            System.out.println("测试删除重复数据1");
            list.addNodeIndex(2,1);
            list.display();
            list.deleteDuplecate(list.head);
            list.display();
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MDgwNzI0Nw_size_16_color_FFFFFF_t_70]: /images/20220123/ec6978f7341e42e6b63c0a16458718d3.png