203. 移除链表元素

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

解题思路

这道题的思路是找到第一个节点值不等于val的节点，然后判断下一个节点的值是否不等于val，，如果不等于，则把当前节点的next链接到下一个节点的下一个节点，以此遍历，直到next节点为空，基于以上考虑，我们可以构建出一个虚拟节点，使其指向head。这样虚拟节点就可以作为第一个节点值不为val的节点，完成上面所说的遍历。

代码

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode node = new ListNode(0,head);
        ListNode temp = node;
        while(temp.next!=null){
            if(temp.next.val == val){
                temp.next = temp.next.next;
            }else{
                temp= temp.next;
            }
        }
        return node.next;
    }
}

总结

这道题如果不采用虚拟节点方式也可以实现，只是需要多一步找到第一个节点值不为val的节点，然后按照以上的判断逻辑去循环遍历好。
需要注意的点：如果当前节点的下一个节点的值等于val，只需要将当前节点的下一个节点指向下一个节点的下一个节点就好，而不用将当前节点赋值到下一个节点。因为我们是判断下一个节点是否满足需求，而赋值后，下一个节点已经是一个新的节点了，可以直接判断

707. 设计链表

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
在链表类中实现这些功能

• get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
• addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
• addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
• addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
• deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

解题思路

这道题可以覆盖了链表的常用操作，我们可以采取单链表或者双链表的方式去实现，而不管是采用单链表和双链表的形式，我们都需要考虑头节点或头尾节点对链表在操作中的影响（对头节点或者头尾节点的特殊处理），基于这一考虑，我们可以通过虚拟头尾节点的方式，来消除这种影响。

代码

单链表

class MyLinkedList {

    private int size;
    private ListNode head;


    public MyLinkedList() {
        size = 0;
        head = new ListNode(-1);
    }
    
    public int get(int index) {
        ListNode listNode = getListNodeByIndex(index+1);
        if(listNode == null){
            return -1;
        }
        return listNode.val;
    }
    
    public void addAtHead(int val) {
        addAtIndex(0,val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(size,val);
    }
    
    public void addAtIndex(int index, int val) {
        if(index>size){
            return;
        }
        if(index <0){
            index = 0;
        }
        ListNode preNode = getListNodeByIndex(index);
        ListNode nextNode = preNode.next;
        preNode.next = new ListNode(val,nextNode);
        size++;
    }
    
    public void deleteAtIndex(int index) {
        if(index<0 || index>=size){
            return;
        }
        if(index == 0){
           head = head.next;
           return;
        }
        ListNode findNode = getListNodeByIndex(index);
        ListNode nextNode = findNode.next.next;
        findNode.next = nextNode;
        size--;
    }

    /**
    获取第index节点，注意：第0个节点为虚拟节点，第一个节点才是真正的第0个节点
    所以index有效的最大值为size而不是size-1
     */
    private ListNode getListNodeByIndex(int index){
        if(index<0 || index>size){
            return null;
        }
        ListNode findNode = head;
        for(int i = 0;i<index;i++){
            findNode = findNode.next;
        }
        return findNode;
    }

    //定义出单链表节点类

    class ListNode{

        public int val;

        public ListNode next;

        public ListNode(){

        }

        public ListNode(int val){
            this(val,null);
        }

        public ListNode(int val,ListNode next){
            this.val = val;
            this.next = next;
        }
    }
}

双链表

class MyLinkedList {

    private int size;
    private ListNode head;
    private ListNode tail;


    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
        tail = new ListNode(0);
        head.nextNode = tail;
        tail.preNode = head;
    }
    
    public int get(int index) {
        if(index<0 || index>=size){
            return -1;
        }
        ListNode findNode = getListNode(index+1);
        return findNode.val;
    }
    
    public void addAtHead(int val) {
        addAtIndex(0,val);
    }
    
    public void addAtTail(int val) {
        addAtIndex(size,val);
    }
    
    public void addAtIndex(int index, int val) {
        if(index>size){
            return;
        }
        if(index<0){
            index = 0;
        }
        ListNode preNode = getListNode(index);
        ListNode next = preNode.nextNode;
        preNode.nextNode = new ListNode(val,preNode,next);
         next.preNode = preNode.nextNode;
        size++;
    }
    
    public void deleteAtIndex(int index) {
        if(index<0||index>=size){
            return;
        }
        ListNode findNode = getListNode(index+1);
        ListNode preNode = findNode.preNode;
        ListNode nextNode = findNode.nextNode;
        preNode.nextNode = nextNode;
        nextNode.preNode = preNode;
        size--;
    }

    /**
    根据index获取到对应的node，注意，这里的index是包含head和tail两个虚拟节点的index
     */
    private ListNode getListNode(int index){
        if(index<0||index>size+1){
            return null;
        }
        ListNode findNode;
        if(index<=size/2){
            findNode = head;
            for(int i=0;i<index;i++){
                findNode = findNode.nextNode;
            }
        }else{
            findNode = tail;
            for(int i = size+1;i>index;i--){
                findNode = findNode.preNode;
            }
        }
        return findNode;
    }

    public class ListNode{
        int val;
        ListNode preNode;
        ListNode nextNode;

        public ListNode(int val){
            this(val,null,null);
        }
        public ListNode(int val,ListNode preNode,ListNode nextNode){
            this.val = val;
            this.preNode = preNode;
            this.nextNode = nextNode;
        }

    }
}

总结

从以上的代码可以看出来，添加虚拟节点可以很好的帮助我们解决收尾问题，因为不管我们怎么操作，首尾节点都不会被删除，需要注意的是，因为我们添加了虚拟节点，所以在获取index节点的时候需要注意到底是获取不包含虚拟节点的index还是获取需要包含虚拟节点的index，例如双链表在添加的时候，我们是需要弄清我们到底是需要获取新添加节点的前一个节点还是后一个节点，这对我们后续处理链表的操作起到了关键的作用。

206. 反转链表

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

思路

看到这道题，我们可以想到想要去反转链表，那我们可以用一个节点记录上一个节点，然后遍历到当前节点时，把当前节点的next赋值给之前记录的上一个节点，那么我们可以想到使用双指针的方式去完成，两个指针分别指向上一个节点和当前节点，然后循环去往后移动，直到当前节点为null，而指向上一个节点的指针指向的节点即为新的头节点

代码

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode temp = null;
        while(head!=null){
            temp = head.next;
            head.next = pre;
            pre = head;
            head = temp;
        }
        return pre;
    }
}

总结

利用双指针的方式可以比较容易的完成这题，我们用head来作为指向当前节点的指针，pre用于指向上一个节点的指针，而pre的初始就是null，这样一直遍历下去，就可以将链表反转，需要注意的是，遍历完成后，head指针指向的为null，而pre指针，指向的才是真正的新的链表的头结点。