面试题18_2：删除链表中重复的节点

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。

• 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
• 注意重复的结点不保留：并不是将重复结点删除到只剩一个，而是重复结点的全部会被删除。所以
• 链表1->2->3->3->4->4->5不是1->2->3->4->5

思路一：采用递归的方法去解决
分为两种情况，第一种如果从第一个节点开始就发生和后面节点相同的情况，则循环跳过所有的相同节点，找到第一个不相同的节点，调用自身返回新的头结点。
第二种情况，如果相邻的节点不相同，则用当前节点指向从下一个节点调用自身方法去检查后面的链表，返回的相应节点，相当于重新构造节点，最后返回头结点。
代码如下：

private class ListNode{
        int val;
        ListNode next = null;
        ListNode(int val){
            this.val = val;
        }
    }

    /**
     * 最简单的方法，递归，从第一个节点每个节点一样的思路
     * 分为两种方式：和相邻节点相同，找到第一个与头节点不同的节点开始递归
     *              和相邻节点不同，保存头节点（用它指向下一个节点，下一个节点由递归得出），从它开始再递归，寻找后面的节点
     * @param pHead
     * @return
     */
    public ListNode deleteDuplication(ListNode pHead)
    {
        if (pHead == null || pHead.next == null){
            return pHead;
        }

        //判断相宁是否相等
        if (pHead.next.val == pHead.val){
            //找到下一个节点是否与第一个节点相同
            ListNode p = pHead.next;
            while (p != null && p.val == pHead.val){
                p = p.next;
            }
            //改变头结点，以同样的规则进行跳跃
            return deleteDuplication(p);
        }else {
            //相邻节点不相等，保存当前节点，从下一个节点开始是递归，相同的规则去检查
            pHead.next = deleteDuplication(pHead.next);
            return pHead;

        }
    }

思路二：采用非递归实现以上思路，关键是添加一个记录断开位置结点的指针pre，以便以后面重新的连接，或者开始头节点的重新选择。通过循环去移位，依然分为两种情况，相邻节点相等和不相等，不相等则用pre记录下当前节点，并移动当前节点位置。相等的话找到第一个不相等的节点，如果pre为空，则重新设立头结点，不为空则指向当前节点。
代码如下：

/**\
     * 以上思路的非递归实现
     * @param pHead
     * @return
     */
    public ListNode deleteDuplication1(ListNode pHead)
    {
        if (pHead == null || pHead.next == null){
            return pHead;
        }
        ListNode pre = null;
        ListNode cur = pHead;
        //验证cur不为空是保证连续一样时，不为空时才能进入该循环，防止一直找不到没有找到不同数字
        while (cur != null && cur.next != null){
            if (cur.val == cur.next.val){
                int val = cur.val;
                //找到与目前第一节点不同的节点
                while (cur != null && cur.val == val){
                    cur = cur.next;
                }
                //头节点重复
                if (pre == null){ pHead = cur;}
                //否则重新连接
                else pre.next = cur;

            }else {
                pre = cur;
                cur = cur.next;
            }
        }
        return pHead;
    }