[思路]链表

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

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

虚拟头节点
双指针
一般涉及三个节点：pre、cur，next :::

基础

包含data和next下一节点指针

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

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

删除节点

注意对头节点进行特判【因为是站在当前节点，判断下一节点是否值相等，相等的话把当前节点的next为下下节点】
不要用for，不知道具体长度，用while
不能直接对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保存一下

删除倒数第k个节点

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

链表相交

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

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

环形链表Ⅱ

还得是数学证明啊

fast每次比slow多移动一个节点，如果在途中相遇证明链表有环
从头结点和相遇节点分别出发一个指针，每次只走一个节点，相遇节点就是环形入口的节点。

最后更新于3个月前