删除链表中重复的节点

题目：

在一个排序的链表中，如何删除重复的节点？例如，链表 1->2->3->3->4->4->5 处理后为 1->2->5

分析：

​ 设置一个preNode，用于记录当前结点的前一个结点，再设置一个布尔变量needDelete，如果当前结点和后一结点的值相同（记该值为dupVal），needDelete 赋值为真。

当needDelete为真时，通过循环往后找到第一个不为 dupVal 的结点，把该结点设置为当前结点，并赋值给preNode.next，即相当于完成了删除操作；而当needDelete为假时，把当前结点和preNode往后移一位即可。

代码：

public class DeleteDuplicateNode {

    public static ListNode deleteDuplication(ListNode pHead) {

        ListNode cur = pHead;
        ListNode pre = null;

        while (cur != null) {
            if (cur.next != null && cur.value == cur.next.value) {
                while (cur.next != null && cur.value == cur.next.value) {
                    cur = cur.next;
                }
                cur = cur.next;

                if (pre == null) {
                    pHead = cur;
                }else{
                    pre.next = cur;
                }
            }else{
                pre = cur;
                cur = cur.next;
            }
        }

        return pHead;
    }

    public static ListNode deleteDuplicate(ListNode pHead) {
        // 空结点或者仅一个结点
        if (pHead == null || pHead.next == null) {
            return pHead;
        }

        ListNode preNode = null;
        ListNode curNode = pHead;

        while (curNode != null) {
            boolean needDelete = false;
            if (curNode.next != null && curNode.value == curNode.next.value) {
                needDelete = true;
            }

            if (!needDelete) {
                //当前结点不重复
                preNode = curNode;
                curNode = curNode.next;
            }else{
                //当前结点重复
                int dupValue = curNode.value;
                ListNode toBeDel = curNode;
                while (toBeDel != null && toBeDel.value == dupValue) {
                    //这里删除暂时不涉及前一结点操作，其实主要是找出后面第一个不重复结点
                    toBeDel = toBeDel.next;
                }

                if (preNode == null) {
                    //说明删除的结点为头结点
                    pHead = toBeDel;
                }else{
                    preNode.next = toBeDel;
                }
                //这个结点还是可能会出现重复的，所以不能=next
                curNode = toBeDel;
            }
        }

        return pHead;
    }
}

完整测试用例：

void test(ListNode pHead) {
    System.out.println("-----------");
    System.out.print("The original list is: ");
    ListNode curr = pHead;
    if (curr != null) {
        while (curr.next != null) {
            System.out.print(curr.value + ",");
            curr = curr.next;
        }
        System.out.println(curr.value);
    } else {
        System.out.println();
    }
    pHead = DeleteDuplicateNode.deleteDuplication(pHead);
    System.out.print("The result list is: ");
    curr = pHead;
    if (curr != null) {
        while (curr.next != null) {
            System.out.print(curr.value + ",");
            curr = curr.next;
        }
        System.out.println(curr.value);
    } else {
        System.out.println();
    }
    System.out.println("-----------");
}


/**
 * 重复结点位于链表头部
 */
void test1() {
    ListNode p4 = new ListNode(3, null);
    ListNode p3 = new ListNode(2, p4);
    ListNode p2 = new ListNode(1, p3);
    ListNode p1 = new ListNode(1, p2);
    test(p1);
}

/**
 * 重复结点位于链表尾部
 */
void test2() {
    ListNode p4 = new ListNode(3, null);
    ListNode p3 = new ListNode(3, p4);
    ListNode p2 = new ListNode(2, p3);
    ListNode p1 = new ListNode(1, p2);
    test(p1);
}

/**
 * 重复结点位于链表中部
 */
void test3() {
    ListNode p4 = new ListNode(3, null);
    ListNode p3 = new ListNode(2, p4);
    ListNode p2 = new ListNode(2, p3);
    ListNode p1 = new ListNode(1, p2);
    test(p1);
}

/**
 * 连续出现重复结点
 */
void test4() {
    ListNode p6 = new ListNode(3, null);
    ListNode p5 = new ListNode(3, p6);
    ListNode p4 = new ListNode(2, p5);
    ListNode p3 = new ListNode(2, p4);
    ListNode p2 = new ListNode(1, p3);
    ListNode p1 = new ListNode(1, p2);
    test(p1);
}

/**
 * 多个重复结点
 */
void test5() {
    ListNode p6 = new ListNode(3, null);
    ListNode p5 = new ListNode(3, p6);
    ListNode p4 = new ListNode(3, p5);
    ListNode p3 = new ListNode(2, p4);
    ListNode p2 = new ListNode(1, p3);
    ListNode p1 = new ListNode(1, p2);
    test(p1);
}

/**
 * 无重复结点
 */
void test6() {
    ListNode p6 = new ListNode(6, null);
    ListNode p5 = new ListNode(5, p6);
    ListNode p4 = new ListNode(4, p5);
    ListNode p3 = new ListNode(3, p4);
    ListNode p2 = new ListNode(2, p3);
    ListNode p1 = new ListNode(1, p2);
    test(p1);
}

/**
 * 单个结点
 */
void test7() {
    ListNode p1 = new ListNode(6, null);
    test(p1);
}

/**
 * null
 */
void test8() {
    ListNode p1 = null;
    test(p1);
}

@Test
public void junitTest() {
//        test1();
//        test2();
//        test3();
//        test4();
//        test5();
//        test6();
//        test7();
    test8();
}