面试题18-2:删除链表中重复的节点

package cn.zxy.interview;

import cn.zxy.interview.utils.ListNode;
import cn.zxy.interview.utils.UtilsLinkedList;
import org.junit.Test;

/**
 * 面试题18:二 删除链表的重复元素
 *
 * 设置三个指针pPre, pCurrent, pNext
 * pPre用于指示前一节点, 用于删除元素后, 把后面的元素接上, pNext用于确定重复元素, 当pNext.value == value时, 说明是重复元素
 */

public class A18_DeleteDuplication {

    @Test
    public void main(){
        ListNode root = UtilsLinkedList.buildRepeat();
        UtilsLinkedList.showList(root);
        deleteDuplication(root);
        UtilsLinkedList.showList(root);

    }

    private void deleteDuplication(ListNode root) {
        if(root == null || root.next == null) return;

        ListNode pCurrent = root.next;
        ListNode pPre = root; //如果从第一个元素就开始重复, 就要通过pPre.next修改root.next
        ListNode pNext = null;

        while(pCurrent != null){
            pNext = pCurrent.next;
            boolean needDelete = false;

            //当下一节点不为空, 且当前节点与下一个节点相同时, 标记删除
            if(pNext != null && pCurrent.value == pNext.value){
                needDelete = true;
            }

            //检查删除标记位 如果不需要删除, 就检查下一个
            if(!needDelete){
                pPre = pCurrent;
                pCurrent = pNext;
            }else {
                int value = pCurrent.value;
                //要删除从该节点开始所有重复的节点, 就是找到接下来第一个不是重复值的节点, 使pPre指向它
                //退出条件 元素值不再重复 OR 到了尾部

                while(pNext != null && pNext.value == value){
                    pNext = pNext.next;
                }
                //找到非重复节点后 两个操作: 让pPre指向该节点; 让pCurrent指向该节点
                //注意 这里不需要对pPre的指向进行操作 完成删除操作后, 要让pPre仍在原来的位置
                //因为中间元素都被删除了, 只有原地不动, pPre才是在pCurrent前一个
                pPre.next = pNext;
                pCurrent = pNext;
            }
        }
    }

}