[数据结构与算法]java - 82. 删除排序链表中的重复元素 II

1、解题思路

注意：这种可能会删除第一个节点的链表，最好加上头节点

1 因为要比较当前指针的下个和下下个节点，因此要在这2个节点均不为空的情况下循环删除
2 当前指针的下个和下下个相等就开始执行删除操作；当前指针的下个和下下个不相等就把当前指针后移一个位置；
3 删除操作：当前指针的下个等于重复值，就让当前指针指向下下个

2、代码实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class Solution {

    public ListNode deleteDuplicates(ListNode head) {
        // 这种可能会删除第一个节点的链表，最好加上头节点
        ListNode headNode = new ListNode(-1, head);
        ListNode currentNode = headNode;
        if (head == null) {
            return null;
        }

        // 要比较当前指针的下个和下下个节点，均不能为空
        while (currentNode.next != null && currentNode.next.next != null) {
            // 当前指针的下个和下下个相等就开始执行删除操作
            if (currentNode.next.val == currentNode.next.next.val){
                int x = currentNode.next.val;
                // 删除重复值x
                while (currentNode.next != null && currentNode.next.val == x){
                    // 当前指针的下个等于重复值，就让当前指针指向下下个
                    currentNode.next = currentNode.next.next;
                }
            }
            else { // 当前指针的下个和下下个不相等就把当前指针后移一个
                currentNode = currentNode.next;
            }

        }
        return headNode.next;
    }
}