1. 删除排序链表中的重复元素

我认为链表元素的关键之处在于在头节点之前添加一个结点。

1. 为什么要这样？

主要是将后面的去除过程都形成相同操作，进而使用循环实现。这样防止头节点不能被删除（可能这里体现的不太明显，到第三题就很明显了）。使用cur.next作为比较项，就不需要记录前一个结点了，并且可以直接删除下一个结点。

2. 该题有一个明显的特征

因为它本来就是升序排列的，所以重复元素是一起出现的。

AC代码

/** * 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) {
        if(head == null || head.next == null) return head;
        ListNode node = new ListNode(0,head);
        ListNode cur = node;
        // 建立一个新的头节点，它的next 指针指向head。
        // 为什么要这样？
        // 主要是将后面的去除过程都形成相同操作，进而使用循环实现。
        // 链表删除重复元素的模板
        while(cur.next != null && cur.next.next != null){
            // 因为它本来就是升序排列的，所以重复元素是一起出现的，所以进行去除时是需要将其去除干净，
            while(cur.next != null && cur.next.next != null && cur.next.val == cur.next.next.val){
                cur.next = cur.next.next;
            }
            // 因为只是删除相同元素，所以不会造成空指针。
            cur = cur.next;
        }
        return node.next;
    }
}

2. 移除链表元素

题目分析

就是删除指定值的元素结点。

1. 我觉得还是在head结点前面加一个结点。

便于删除。

2. 注意点

需要注意的是删除的时候会导致空指针，因为可能删除的是最后一个结点。所以在移动到下一个结点，以及删除完毕时需要进行防空判断。

if(cur != null) cur = cur.next;
if(cur == null) break;

AC代码

/** * 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 removeElements(ListNode head, int val) {
        if(head == null) return head;
        if(head.next == null){
            if(head.val == val){
                return null;
            }else{
                return head;
            }
        }
        ListNode node = new ListNode(0,head);
        ListNode cur = node;
        // 删除相应元素的模板
        while(cur.next != null){
            while(cur.next != null && cur.next.val == val){
                cur.next = cur.next.next;
            }
            // 因为和删除重复元素不一样，它只要该元素的值为相应值，就会进行删除，但会造成空指针。
            if(cur != null) cur = cur.next;
            if(cur == null) break;
        }
        return node.next;
    }
}

3. 删除排序链表中的重复元素 II

题目分析

本题唯一的和第一题不同的是该题需要对重复的元素全部删除，那么如果在头节点前不加一个结点就会导致删除不彻底。所以可见加一个结点的好处。

AC代码

/** * 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) {
        // 可以重新创建一个新的结点的next指向头节点
        // 这样防止头节点不能被删除
        // 使用cur.next作为比较项，就不需要记录前一个结点了，并且可以直接删除下一个结点
        if(head == null) return head;
        ListNode node = new ListNode(0,head);
        ListNode cur = node;
        while(cur.next != null && cur.next.next != null){
            if(cur.next.val == cur.next.next.val){
                int x = cur.next.val;
                while(cur.next != null && cur.next.val == x){
                    cur.next = cur.next.next;
                }
            }else{
                cur = cur.next;
            }
        }
        return node.next;
    }
}