剑指Offer_56_删除链表中重复的结点

题目描述

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

解题思路

利用一个指针指向当前需要检查的结点p的前一个指针pre，对于当前要检查的结点p，对后面的结点进行遍历，直到找到与之不同的结点，如果存在相同的结点，那么p的前一个结点指向找到的不同于的p的结点，删除p和其重复的值，然后p指向pre的下一个结点（找到的不同于原来p的结点），继续判断，直到链表的末尾。

实现

/*链表结点的定义*/
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
/*实现*/
public class Solution {
    public ListNode deleteDuplication(ListNode pHead)
    {
        ListNode pre = null, p = pHead;
        if (pHead == null || pHead.next == null) return pHead;
        while (p != null){
            ListNode q = p.next;
            int count = 0;
            while (q!=null && q.val == p.val){
                q = q.next;
                count ++;
            }

            if (count > 0){
                //有重复的
                if (pre == null) pHead = q;
                else pre.next = q;
            }else {
                if (pre == null) pHead = p;
                pre = p;
            }

            p = q;

        }

        return pHead;
    }
}