代码随想录算法训练营，8月30日 | 203.移除链表元素， 707.设计链表， 206.反转链表

链表理论基础
1.单链表：数据域和指针域（指向下一个结点的位置）组成，头结点，结尾为空指针；双链表：多了一个指向前一个结点的指针；循环链表：结尾指向头结点。
2.链表在内存中的存储不是顺序的，跟数组不同，要找一个数据只能通过前一个数据来找，所有这就导致链表的查询比数组麻烦，但是插入删除数据却更方便（只用修改前面的数据的指针，以及将自己的指针指向下一个数据）。
3.Java里定义一个链表：

public class ListNode {
    int val;
    ListNode next;

    // 节点的构造函数(无参)
    public ListNode() {
    }
    // 节点的构造函数(有一个参数)
    public ListNode(int val) {
        this.val = val;
    }
    // 节点的构造函数(有两个参数)
    public ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

203.移除链表元素
题目链接：203.移除链表元素
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰移除链表元素
日期：2024-08-30

思路：1.移除链表的元素想到链表的结构，将要移除的元素的前一个元素的指针变成指向它的下一个元素的就行了，但还要考虑到头结点没有前一个元素，单独提出来操作；
2.增加一个虚拟头结点指向头结点就可以免去单独操作头结点的操作。
Java代码如下：

//原数组上操作
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        while(head != null && head.val == val){
            head = head.next;
        }
        ListNode cur = head;
        while(cur != null && cur.next != null){
            if(cur.next.val == val){
                cur.next = cur.next.next;
            }else{
                cur = cur.next;
            }
        }
        return head;
    }
}

//虚拟头结点
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;
        ListNode cur = dummyHead;
        while(cur != null && cur.next != null){
            if(cur.next.val == val){
                cur.next = cur.next.next;
            }else{
                cur = cur.next;
            }
        }
        return dummyHead.next;//注意这个才是新的头结点
    }
}

总结：链表很多时候都要考虑特殊的那个头结点，加一个虚拟的头结点就让它不特殊了，可以像其他结点一样操作

707.设计链表
题目链接：707.设计链表
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰设计链表
日期：2024-08-30

思路：首先这道题要先知道Java中链表的结构是怎么定义的，清楚了后再考虑是不是能用虚拟头结点来避免很多有关头结点的讨论，还有一点就是既然有要求再index这个位置插入，那么我必须知道index这个值到底在不在链表中，所有我们在定义MyLinkedList时还要考虑一个size这个值，并且后面增删也要对应的改动。
Java代码如下：

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 {
    int size;
    ListNode dummyHead;
    public MyLinkedList() {
        dummyHead = new ListNode(0);//这是一个虚拟头结点
        size = 0;
    }
    
    public int get(int index) {
        if(index < 0 || index > size - 1){
            return -1;
        }
        ListNode cur = dummyHead;
        for(int i = 0; i < index + 1; i++){//这里的是index + 1
            cur = cur.next;
        }
        return cur.val;
    }
    
    public void addAtHead(int val) {
        ListNode node = new ListNode(val);
        node.next = dummyHead.next;
        dummyHead.next = node;
        size++;
    }
    
    public void addAtTail(int val) {
        ListNode node = new ListNode(val);
        ListNode cur = dummyHead;
        while(cur.next != null){
            cur = cur.next;
        }
        cur.next = node;
        size++;
    }
    
    public void addAtIndex(int index, int val) {
        if(index < 0 ){
            index = 0;
        }
        if(index > size){
            return;
        }
        ListNode node = new ListNode(val);
        ListNode cur = dummyHead;
        for(int i = 0; i < index; i++){
            cur = cur.next;
        }
        node.next = cur.next;
        cur.next = node;
        size++;
    }
    
    public void deleteAtIndex(int index) {
        if(index < 0 || index > size - 1){
            return;
        }
        ListNode cur = dummyHead;
        for(int i = 0; i < index; i++){
            cur = cur.next;
        }
        cur.next = cur.next.next;
        size--;
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */

总结：清楚了链表的定义以及用了虚拟头结点后就比较容易了，增删也是些基本的操作。

206.反转链表
题目链接：206.反转链表
文档讲解︰代码随想录(programmercarl.com)
视频讲解︰反转链表
日期：2024-08-30

思路：直接在链表原本上操作，改下指针的方向，从头开始的话cur = head，cur要指向null（pre前一个结点），但这之前要保留下cur.next，反转完了，pre变为cur，cur变为之前保留的那个后续的结点，直到cur.next为null。
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 reverseList(ListNode head) {
        ListNode cur = head;
        ListNode pre = null;
        ListNode temp = null;
        while(cur != null){
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

总结：实际上手时while判定出错了，while里面已经将cur设置为了后一位，所有判定条件直接是cur != null就行，而不是cur.next；最后返回的值pre才是头的位置，第一次想当然以为是cur。