迭代

双指针

思想如下:进行特殊判断之后,利用pre来维护一个不含重复值的链表,cur则遍历整条链表。对于这个排序链表,若cur的值与pre当前值不同,则把cur加入到pre中,否则让pre指向空。遍历结束之后返回head。

这是我一开始想到的做法,其实有些步骤很多余,并且不是最优的。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode pre = head, cur = head.next;
        while(cur != null){
            if(pre.val != cur.val){
                // 把该结点连接到pre的后面
                pre.next = cur;
                pre = cur;
            }else{
                // 不然就置空,防止[1,2,2,2]这种情况
                pre.next = null;
            }
            // cur一直向前遍历
            cur = cur.next;
        } 
        return head;
    }
}

优化:单指针解决

仅用一个cur指针遍历解决。
因为它要求每个元素仅出现一次,如果当前元素与下一个相同,则把下一个删掉;当不同的时候才继续前往遍历……

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode cur = head;
        while(cur != null && cur.next != null){
            if(cur.val == cur.next.val){
                // 下一个与当前相同,则把下一个删掉,仅保留当前元素
                cur.next = cur.next.next;
            }else{
                // 与下一个的值不同,才前进
                cur = cur.next;
            }
        }
        return head;
    }
}