一，问题描述
请自己构造一个简单的有序单链表，然后实现删除链表中的重复结点。比如：
二，问题分析
首先要实现一个单链表，因此需要定义一个节点类Node。其次，实现向链表中添加结点的方法(使用尾插法)addNode
删除重复结点的实现思路：
定义两个指针：pre 和 next。初始时，pre指向链表中的第一个元素，next指向链表中的第二个元素。如果 pre 的值与 next 的值不相等，则两个指针分别都向后移一个结点；若相等，则删除 next 指针指向的结点即可。
三，整个代码实现
// delete duplicated nodes in increased list public 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); } }
本文转自hapjin博客园博客，原文链接：http://www.cnblogs.com/hapjin/，如需转载请自行联系原作者
