1. 移除链表元素(LeetCode 233)

题目：删除链表中等于给定值 val 的所有节点。

示例 1： 输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
示例 2： 输入：head = [], val = 1 输出：[]
示例 3： 输入：head = [7,7,7,7], val = 7 输出：[]

思路：

• 设置虚拟节点：这样对头节点和后面节点的处理是一致的（都有前驱节点）
• C++/C需要对删除的节点进行内存释放；java不需要程序员手动操作，内存机制会自动释放。

/**
 * 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) {
        // 在原来的链表前面设置一个虚拟头节点
        ListNode newhead = new ListNode(0,head);
        ListNode pre = newhead;
        ListNode current = newhead.next;
        while(current != null){
            if(current.val == val) {
                pre.next = current.next;
            }else {
                pre = current;
            }
            current = current.next;
        }
        return newhead.next;
    }
}

2. 设计链表(LeetCode 707)

题目：详见LeetCode
注意：

• 注意index的边界条件判断
• 这里的index定义和数组相同，是从0开始的

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 MyLinkedList {
    ListNode dummy_head;    //虚拟头节点
    int size;

    public MyLinkedList() {
        this.dummy_head = new ListNode(0,null);
        this.size = 0;
    }
    
    public int get(int index) {
        int count = 0;
        if(index < 0 || index >= this.size ) return -1;
        ListNode cur = dummy_head.next;
        while(count < index){
            count++;
            cur = cur.next;
        }
        return cur.val;
    }
    
    public void addAtHead(int val) {
        ListNode newnode = new ListNode(val,dummy_head.next);
        this.dummy_head.next = newnode;
        this.size++;
    }
    
    public void addAtTail(int val) {
        ListNode newnode = new ListNode(val,null);
        ListNode cur = this.dummy_head.next;
        if(this.size == 0){
            dummy_head.next = newnode;
            this.size++;
            return;
        }
        while(cur.next != null){
            cur = cur.next;
        }
        cur.next = newnode;
        this.size++;
        return;
    }
    
    public void addAtIndex(int index, int val) {
        if(index > this.size) return;
        else if(index <= 0){
            addAtHead(val);
            return;
        }else if(index  == this.size){
            addAtTail(val);
            return;
        }
        int count = 0;
        ListNode cur = this.dummy_head.next;
        while(count < index-1) {
            cur = cur.next;
            count++;
        }
        ListNode newNode = new ListNode(val, cur.next);
        cur.next = newNode;
        this.size++;
    }
    
    public void deleteAtIndex(int index) {
        if(index < 0 || index >= this.size) return;
        int count = -1;
        ListNode pre = this.dummy_head;
        while(count < index-1){
            pre = pre.next;
            count++;
        }
        pre.next = pre.next.next;
        this.size--;
    }
}