package algorithms;

 /*

 public class ListNode {

    int val;

    ListNode next = null;

    ListNode(int val) {

        this.val = val;

    }

 }

 */

 /*

  *

  * 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，

 重复的结点不保留，返回链表头指针。(认真审题)

 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

 从头遍历整个链表 如果当前节点pNode的值与下一个节点相同

 那么他们就是重复的节点  需要被删除

 为了保证删除之后的链表仍然是相连的

 需要把当前节点的前一个节点pPreNode保存起来

 循环的过程中确保pPreNode始终与下一个没有重复的节点连接在一起

 */

 public class DeleteDuplication {

     public ListNode deleteDuplication(ListNode pHead) {

         ListNode pPreNode = null;

         ListNode pNode = pHead;

         while (pNode != null) {

             ListNode pNext = pNode.next;

             boolean needDelete = false;

             if (pNext != null && pNext.val == pNode.val)

                 needDelete = true;

             if (!needDelete) {

                 pPreNode = pNode;

                 pNode = pNode.next;

             } else {

                 ListNode pDeleteNode = pNode;

                 int value = pDeleteNode.val;

                 while (pDeleteNode != null && pDeleteNode.val == value) {

                     pNext = pDeleteNode.next;

                     pDeleteNode = pNext;

                 }

                 if (pPreNode == null)

                     pHead = pNext;

                 else

                     pPreNode.next = pNext;

                 pNode = pNext;

             }

         }

         return pHead;

     }

 }