55 删除链表中重复的结点

题目描述

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

代码一

思路:就是不断的遍历,有个特殊情况就是当头节点就出现重复值的时候.

public ListNode deleteDuplication(ListNode pHead)
    {
        ListNode head = new ListNode(Integer.MIN_VALUE);
        head.next = pHead;//这里的目的是为了防止在头部就出现重复的节点
        ListNode p = pHead;
        ListNode pre = head;
        while(p!=null) {
            if(p.next!=null&&p.val==p.next.val) {
                while(p.next!=null&&p.val==p.next.val) {
                    p=p.next;
                }
                p = p.next;
                pre.next = p;
            }else {                
                pre = p;
                p=p.next;
            }
        }
        return head.next;
    }

代码二

思想:递归

public ListNode deleteDuplication(ListNode pHead)
    {
        if(pHead==null||pHead.next==null)return pHead;
        if(pHead.val==pHead.next.val) {
            ListNode node = pHead.next;
            while(node!=null&&node.val==pHead.val) {
                node = node.next;
            }
             // 从不重复的结点继续递归，并且这个节点也是上次递归的返回值
            return deleteDuplication(node);
        }else {
             //继续递归下一个节点。返回的是不重复的节点，因此直接连起来就好
            pHead.next = deleteDuplication(pHead.next);
            return pHead;
        }
    }