题解 | #删除链表中重复的结点#

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
// 由于链表已经排序，重复值是连在一起的，所以遍历一遍，直接比较即可
// 虽然存在内循环，但是跳跃式的，可以替代原本的外循环，因此时间复杂度为O（n），空间复杂度为O（1）
public class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
    	// 设置两个虚头结点
        ListNode node_1 = new ListNode(-1);
        ListNode node0 = new ListNode(-2);
        ListNode node = pHead;
        node_1.next = node0;
        node0.next = node;
        
        ListNode returnHead = node0; // 由于原来的头结点可能被删掉，需要使用虚头结点的next返回
        int val = -2; // 用于保存重复值
        
        while(node != null){
            if(node.val != node0.val){
                node_1 = node0;
                node0 = node;
                node = node.next;
            }
            else{
                val = node.val;
                // 出现重复时，node前进至不重复点，然后node_1直接跨过重复点连至node
                while(node != null && node.val == val){
                    node = node.next;
                }
                node_1.next = node;
                // 判断是否需要继续遍历，需要则调整node0和node的位置
                if(node != null){
                    node0 = node;
                    node = node.next;
                }
            }
        }
        return returnHead.next;
    }
}