[数据结构与算法]代码随想录算法训练营第三天|203.移除链表元素，707.设计链表，206.反转链表

1、移除链表元素

题目链接/文章讲解/视频讲解：
https://programmercarl.com/0203.%E7%A7%BB%E9%99%A4%E9%93%BE%E8%A1%A8%E5%85%83%E7%B4%A0.html

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

思路：
1、注意这里的头节点就是链表存储的第一个值，因此可以声明一个哑节点指向链表的头节点。
2、由题意，遍历整个链表，当节点的值等于val时，就删除这个节点。
3、为了方便删除，考虑将指针指向前一个节点，利用p.next来检查下一个节点是否满足要求，同时用p.next=p.next.next的方式来删除满足要求的节点。
4、注意，在删除节点后，p.next就已经改变，因此不需要再赋值p=p.next，而没有删除时，则需要p=p.next向后移动。

/**
 * 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 dummy = new ListNode(0);
        dummy.next = head;
        ListNode p = dummy;
        while (p.next != null) {
            if (p.next.val == val) {
                p.next = p.next.next;
            } else {
                p = p.next;
            }
        }
        return dummy.next;
    }
}

2、设计链表

题目链接/文章讲解/视频讲解：
https://programmercarl.com/0707.%E8%AE%BE%E8%AE%A1%E9%93%BE%E8%A1%A8.html

class MyLinkedList {

    int size;
    LinkNode head;

    public MyLinkedList() {
        size = 0;
        head = new LinkNode(0);
    }
    
    public int get(int index) {
        if (index < 0 || index >= size) {
            return -1;
        }
        LinkNode currentNode = head;
        for (int i = 0; i <= index; i++) {
            currentNode = currentNode.next;
        }
        return currentNode.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;
        }
        size++;
        LinkNode pred = head;
        for (int i = 0; i < index; i++) {
            pred = pred.next;
        }
        LinkNode toAdd = new LinkNode(val);
        toAdd.next = pred.next;
        pred.next = toAdd;
    }
    
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        size--;
        LinkNode pred = head;
        for (int i = 0; i < index; i++) {
            pred = pred.next;
        }
        pred.next = pred.next.next;
    }
}

class LinkNode {
    int val;
    LinkNode next;
    public LinkNode() {
        next = null;
    }
    public LinkNode(int val) {
        this.val = val;
        next = null;
    }
}

3、反转链表

题目链接/文章讲解/视频讲解：
https://programmercarl.com/0206.%E7%BF%BB%E8%BD%AC%E9%93%BE%E8%A1%A8.html

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

思路：
1、新建一个链表头，每次都从输入的链表中取出头节点，并将它按照头部添加的方法加入新的链表。
2、声明一个哑节点指向输入的链表，一个指针转门指向要从输入链表中提取的头节点，一个新节点转门指向输出链表的头节点。

/**
 * 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 reverseList(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode ansHead = new ListNode(0);
        ListNode temp = head;
        while (dummy.next != null) {
            dummy.next = dummy.next.next;
            temp.next = ansHead.next;
            ansHead.next = temp;
            temp = dummy.next;
        }
        return ansHead.next;
    }
}