首页 > 代码库 > 删除有序链表中的重复结点

删除有序链表中的重复结点

一,问题描述

请自己构造一个简单的有序单链表,然后实现删除链表中的重复结点。比如:

技术分享

 

二,问题分析

首先要实现一个单链表,因此需要定义一个节点类Node。其次,实现向链表中添加结点的方法(使用尾插法)addNode

删除重复结点的实现思路:

定义两个指针:pre 和 next。初始时,pre指向链表中的第一个元素,next指向链表中的第二个元素。如果 pre 的值与 next 的值不相等,则两个指针分别都向后移一个结点;若相等,则删除 next 指针指向的结点即可。

 

三,整个代码实现

// delete duplicated nodes in increased listpublic class MyLinkedList {    private class Node{        int ele;        Node next;        public Node(int ele) {            this.ele = ele;            next = null;        }    }        private Node head;    private Node tail;        //采用尾插法添加结点    public void addNode(int ele){        Node newNode = new Node(ele);        if(tail != null)            tail.next = newNode;        else{// first node            head = newNode;        }        tail = newNode;    }        //删除有序单链表中的重复结点    public void delDuplicatedNode(){        if(head == null)            return;        Node pre,next;        pre = head;        next = head.next;                while(next != null)        {            if(pre.ele != next.ele)            {                pre = next;                next = next.next;            }else{//delete next point node                Node delNode = next;                pre.next = next.next;                next = next.next;                delNode.next = null;//avoid memory leak//                delNode = null;            }        }    }        @Override    public String toString() {        if(head == null)            return "null";        Node current = head;        StringBuilder sb = new StringBuilder();        while(current != null){            sb.append(current.ele + " ");            current = current.next;        }        return sb.toString();    }        //hapjin test    public static void main(String[] args) {        MyLinkedList mylist = new MyLinkedList();        int[] eles = {1,2,3,3,4,4,5};        for (int ele : eles) {            mylist.addNode(ele);        }        System.out.println("before del: " + mylist);        mylist.delDuplicatedNode();        System.out.println("after del: " + mylist);    }}

 

删除有序链表中的重复结点