一.删除链表中等于给定值 val 的所有节点

在做这道题之前，我们先来看一下这道题的简化版本：

1.1 删除链表中等于给定值 val 的第一个结点

题目分析：

其核心其实就是把要删除的结点的前驱找到，让前驱的指针域指向删除结点的后继（这时，要删除的结点因为没有被任何结点所引用，被回收了），即可完成任务。

public Node checkKeyIndex(int key) {
        ListNode cur = head;
        //这里使用cur.next 是为了避免空指针访问异常
        while(cur.next != null) {
             if(cur.next.val == key) {
                 return cur;
             }
        }
        return null;
}    
public void remove(int key) {
        // 判断头的数据域是否为需要寻找的值
        if(head.val == key) {
            head = head.next;
            return;
        }
        ListNode prevDel = checkKeyIndex(key);
        if(prevDel == null) {
            System.out.println("找不到这个元素");
        }
        ListNode del = prevDel.next;
        prevDel.next = del.next;
        //上两行代码也可以用这行替换： prevDel = prevDel.next.next;
}

1.2 进入正题

题目描述：

给你一个链表的头节点?head?和一个整数?val?，请你删除链表中所有满足?Node.val == val?的节点，并返回?新的头节点?。

?分析：

我们可以使用双指针的方法，这时只需遍历一遍链表即可。

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //先判断 所给头是否为空
        if(head == null) {
            return null;
        }
        ListNode cur = head.next;
        ListNode prev = head;
        while(cur != null) {
            if(cur.val == val) {
                prev.next = cur.next;
                cur = cur.next;
            } else {
                prev = cur;
                cur = cur.next;
            }
        }
        //最后判断头的数据域是否为需要删除元素，如果放在前面则相当于没判断
        if(head.val == val) {
            head = head.next;
        }
        return head; 
    }       
}

?题目链接：移除链表元素

二、反转链表

给你单链表的头节点?head?，请你反转链表，并返回反转后的链表。

?题目分析：使用头插法的思想，准备两个指针变量，head和 cur，遍历一遍链表，在cur.next = head之后，新的头结点就需要被改变，即head = cur。

class Solution {
    public ListNode reverseList(ListNode head) {
        if(head == null) {
            return null;
        }
        if(head.next == null) {
            return head;
        }
        //以下两步操作不能够调换，如果调换的话，头节点之后的结点会丢失
        ListNode cur = head.next;
        head.next = null;
        //为了防止在头插法完成之后，后续链表因没被引用而丢失的问题。建立一个变量来存储
        while(cur != null) {
            ListNode curNext = cur.next;
            cur.next = head;//进行头插法
            head = cur;
            cur = curNext;//注意这里只能使用cur = curNext 
            //不能使用cur = cur.next 因为这时cur.next已经存储的是另一个值了
        }
        return head;
    }
}

题目链接：反转链表