链表

• 定义:通过指针串联在一起的线性结构，每一个节点由两个部分组成：数据域和指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null，即为空指针。

链表类型

1. 单链表
2. 双链表
3. 循环链表，即链表首尾相连，可以解决约瑟夫环问题

链表的存储方式

数组在内存中是连续分布的，但是链表在内存中不是连续分布的

链表的定义

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.）

1. 有虚拟节点方式；记得head为val值的边缘条件，以及target指针的空指针问题

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

2. 无虚拟节点方式；先对head指向的值处理，在运行到非val值后扫描后指针

/**
无虚拟节点方式；先对head指向的值处理，在运行到非val值后扫描后指针
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
       //先将head指针处理至不为val值的地方
       while(head != null && head.val == val){
           head = head.next;
       }
       //head为空，则直接返回
       if(head == null){
           return head;
       }
        ListNode pre = head;
        ListNode post = head.next;
        while(post != null){
            if(post.val == val){
                pre.next = post.next;
            }else{
                pre = post;
            }
            post = post.next;
        }
        return head;
    }
}

设计链表：实现五个函数（力扣707.）

获取第n个节点的数值

• 使用虚拟头结点的方式 dummynode
• while(n)
• cur = cur.next;
• n--

头部插入节点

• new一个新node
• newNode.next=dummyHead.next;(注意顺序)
• dummyhead.next=newNode;
• size++；

尾部插入节点

• cur = dummyhead；
• while(cur.next == null)
• cur = cur.next;
• cur.next = newNode

第n个节点的插入

• cur应该指向第n个节点的前一个结点
• cur = dummyhead
• while(n)
• cur = cur.next;
• n--;
• newNode.next=cur.next;
• cur.next=newNode;
• size++;

第n个节点的删除

• 判断n的合法性
• cur= dummyhead;
• while(n)
• cur = cur.next;
• n--;
• cur.next=cur.next.next;
• return dummyhead.next;

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

class MyLinkedList {//带有头结点的链表
    //容量大小
    int size;
    //虚拟头结点
    ListNode dummyhead;

    public MyLinkedList() {
        //初始化单链表
        size = 0;
        dummyhead = new ListNode(0);
    }
    
    public int get(int index) {
        if(index < 0 || index >= size){
            return -1;
        }
        ListNode current = dummyhead;
        while(index >= 0){
            current = current.next;
            index --;
        }
        return current.val;
    }
    
    public void addAtHead(int val) {
        ListNode current = dummyhead;
        ListNode target = new ListNode(val);
        target.next = current.next;
        current.next = target;
        size++;
    }
    
    public void addAtTail(int val) {
        ListNode current = dummyhead;
        while(current.next != null){
            current = current.next;
        }
        ListNode target = new ListNode(val);
        target.next = null;
        current.next = target;
        size++;
    }
    
    public void addAtIndex(int index, int val) {
        if(index < 0 || index >= size + 1){
            return;
        }
        ListNode current = dummyhead;
        while(index > 0){
            current = current.next;
            index--;
        }
        ListNode target = new ListNode(val);
        target.next = current.next;
        current.next = target;
        size++;
    }
    
    public void deleteAtIndex(int index) {
        if(index < 0 || index >= size){
            return;
        }
        ListNode current = dummyhead;
        while(index > 0){
            current = current.next;
            index--;
        }
        current.next = current.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.）

• 遍历数组＋头插法

/**
 * 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 pummyhead = new ListNode();
        // pummyhead.next = head;
        if(head == null){
            return null;
        }
        ListNode from = head.next;

        ListNode targetPummyHead = new ListNode();
        ListNode current = targetPummyHead;
        while(head != null){
            head.next = targetPummyHead.next;
            targetPummyHead.next = head;

            head = from;
            if(from != null){
                from = from.next;
            }else{from = null;}
        }
        return targetPummyHead.next;
    }
}

• 双指针写法

1. 初始化：cur = head;pre=null;
2. 遍历链表：while(cur != null)
3. 需要一个临时指针temp = cur.next
4. cur.next=pre;
5. pre=cur;
6. cur=temp
7. return pre;

class Solution {
    public ListNode reverseList(ListNode head) {
       //双指针思路
       //初始化
       ListNode pre = null;
       ListNode cur = head;
       while( cur != null){
           ListNode temp = cur.next;
           cur.next = pre;
           pre = cur;
           cur = temp;
       }
       return pre;
    }
}

• 递归算法

1. reverse(cur,pre){
2. if(cur == null)return pre;//此时终止
3. temp = cur.next;
4. cur.next=pre;
5. reverse(temp,cur)}
6. //使用：return reverse（head,null);

其实内核解法与双指针解法相同

class Solution {
    public ListNode reverseList(ListNode head) {
        return reverse(null,head);
    }
    public ListNode reverse(ListNode pre,ListNode current){
        if(current == null){
            return pre;//递归的终止条件为current为null
        }
        ListNode temp = current.next;//临时节点暂存
        current.next = pre;
        return reverse(current,temp);
    }
}

本栏目推荐文章
• 2024/1/13 算法笔记
• 代码随想录 day18 找树左下角的值 路径总和 从中序与后序遍历序列构造二叉树
• Openharmony 跑 CV 算法
• .NET中的加密算法总结(自定义加密Helper类续)
• 算法练习题
• 算法学习Day26组合总和、分割回文串
• （坚持每天写算法）基础算法复习与学习part1基础算法1-7——高精度减法（处理t=1和t>1代码的写法，t为操作次数）
• 【SPFA】最短路的一种算法
• [代码随想录] 第四天
• darknet-yolov4训练自己的模型记录

随想录 训练营 随想 算法 元素最大值 训练营 随想 元素 训练营 随想 元素 代码 随想录 训练营 随想 算法 算法 随想录 训练营 随想 算法 随想录 训练营 序列 训练营 随想 元素 温度 算法 随想录 训练营 数组 算法 随想录 训练营 总和 算法 随想录 队列 训练营 算法 随想录 训练营 九天