[思路]链表

本篇博客只记录刷题思路不记录具体代码 题目来源代码随想录 刷完感想：奖励今天喝中药调理脑子🙂

:::tip 和链表题相关的提示

1. 虚拟头节点

2. 双指针

3. 一般涉及三个节点：pre、cur，next :::

基础

包含data和next下一节点指针

新增：cur.next = new;new.next = next;【这里就涉及到一个保存操作】

删除：cur.next = cur.next.next

删除节点

1. 注意对头节点进行特判【因为是站在当前节点，判断下一节点是否值相等，相等的话把当前节点的next为下下节点】

2. 不要用for，不知道具体长度，用while

3. 不能直接对head操作，而是新建一个链表节点

设计链表

感觉没什么好说的，记得用虚拟头节点

show code

//单链表
class ListNode {
    int val;
    ListNode next;
    ListNode(){}
    ListNode(int val) {
        this.val=val;
    }
}
class MyLinkedList {
    //size存储链表元素的个数
    int size;
    //虚拟头结点
    ListNode head;

    //初始化链表
    public MyLinkedList() {
        size = 0;
        head = new ListNode(0);
    }

    //获取第index个节点的数值，注意index是从0开始的，第0个节点就是头结点
    public int get(int index) {
        //如果index非法，返回-1
        if (index < 0 || index >= size) {
            return -1;
        }
        ListNode currentNode = head;
        //包含一个虚拟头节点，所以查找第 index+1 个节点
        for (int i = 0; i <= index; i++) {
            currentNode = currentNode.next;
        }
        return currentNode.val;
    }

    // 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
    // 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点
    // 如果 index 大于链表的长度，则返回空
    public void addAtIndex(int index, int val) {
        if (index > size) {
            return;
        }
        if (index < 0) {
            index = 0;
        }
        size++;
        //找到要插入节点的前驱
        ListNode pred = head;
        for (int i = 0; i < index; i++) {
            pred = pred.next;
        }
        ListNode toAdd = new ListNode(val);
        toAdd.next = pred.next;
        pred.next = toAdd;
    }

    //删除第index个节点
    public void deleteAtIndex(int index) {
        if (index < 0 || index >= size) {
            return;
        }
        size--;
        //因为有虚拟头节点，所以不用对Index=0的情况进行特殊处理
        ListNode pred = head;
        for (int i = 0; i < index ; i++) {
            pred = pred.next;
        }
        pred.next = pred.next.next;
    }
}

翻转链表

还是【因为是站在当前节点，判断下一节点是否值相等，相等的话把当前节点的next为下下节点】的思路

所以必须要有三个参数：pre、cur，next

// 更新节点next
next = cur.next
cur.next = pre
// 更新节点
cur = next
pre = cur

两两交换链表

表面涉及两个节点，实际上涉及到了四个节点(考虑next ，所以也加上虚拟头节点)

所以就按照模拟逻辑一个个交换就好了

但是要注意保存节点（1，3），因为在更改cur节点next为2的同时，1是被独立了，得temp保存一下

img

删除倒数第k个节点

双指针中的快慢指针思路，还没忘记，真不错

链表相交

为啥这道题就忘记了要用双指针、、、

这种涉及到两个位置差的就很适合快慢指针

环形链表Ⅱ

还得是数学证明啊

1. fast每次比slow多移动一个节点，如果在途中相遇证明链表有环

2. 从头结点和相遇节点分别出发一个指针，每次只走一个节点， 相遇节点就是环形入口的节点。