删除链表中的重复结点

编程练习

题目：在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

思路：通过将链表各节点装入ArrayList来方便处理，将ArrayList中的node节点遍历，发现有前后值相同的结点都做删除，然后将整理后的list再重新加上前后的Node之间的链接关系，注意需要将list中最后一个节点的next赋值为null，不然即使在list中删除了最后一个节点后重复出现的结点，如果引用还在，就还能输出后边的重复结点。
此外，还需要对特殊情况：比如只含有一个节点或者所有节点的值均相同的情况做不同的处理。
java代码如下：

import java.util.ArrayList;

public class DeleteDuplication {
	public static ListNode deleteDuplication(ListNode pHead){
		
		ArrayList<ListNode> list =new ArrayList<ListNode>();
		//将链表装入ArrayList
		while(pHead!=null) {
			list.add(pHead);
			pHead=pHead.next;
		}
		//如果只有一个节点
		if(list.size()==1) {
			return list.get(0);
		}
		//如果全部结点的值都相同
		int count=0;
		for(int i=0;i<list.size();i++) {
			if(list.get(i).val==list.get(0).val) {
				count++;
			}
		}
		if(count==list.size()) {
			pHead=null;
			return pHead;
		}
		//删除重复结点
		for(int i=0;i<list.size();i++) {
			if(list.get(i)!=null && list.get(i).next!=null) {
				if(list.get(i).val==list.get(i).next.val) {
					list.remove(i);
					list.remove(i);
					i=-1; //每次删除重复结点后list的size改变，需要将上面的i重置为0，所以这里的i需要设置为-1，因为每次循环i都会+1.
				}
			}
		}
		if(list.size()==0) {
			pHead=null;
			return pHead;
		}
		for(int i=0;i<list.size()-1;i++) {
			list.get(i).next=list.get(i+1);
		}
		list.get(list.size()-1).next=null;//清理最后一个节点之后的重复结点的引用
		return list.get(0);
    }
	public static void main(String[] args) {
		ListNode l1=new ListNode(1);
		ListNode l2=new ListNode(1);
		ListNode l3=new ListNode(2);
		ListNode l4=new ListNode(3);
		ListNode l5=new ListNode(3);
		ListNode l6=new ListNode(4);
		ListNode l7=new ListNode(5);
		ListNode l8=new ListNode(5);
		
		
		l1.next=l2;
		l2.next=l3;
		l3.next=l4;
		l4.next=l5;
		l5.next=l6;
		l6.next=l7;
		l7.next=l8;
		l8.next=null;
		System.out.println(deleteDuplication(l1));
		
	}

}