做网站公司能赚钱吗,沧州建网站,新闻热点事件,asp网站如何安装【算法系列-链表】设计链表 文章目录 【算法系列-链表】设计链表1. 算法分析#x1f6f8;2. 解题过程#x1f3ac;2.1 初始化2.1.1 思路分析#x1f3af;2.1.2 代码示例#x1f330; 2.2 get(获取第n个节点的值)2.2.1 思路分析#x1f3af;2.2.2 代码示例#x1f330; 2.…【算法系列-链表】设计链表 文章目录 【算法系列-链表】设计链表1. 算法分析2. 解题过程2.1 初始化2.1.1 思路分析2.1.2 代码示例 2.2 get(获取第n个节点的值)2.2.1 思路分析2.2.2 代码示例 2.3 addAtHead(头部插入节点)2.3.1 思路分析2.3.2 代码示例 2.4 addAtTail(尾部插入节点)2.4.1 思路分析2.4.2 代码示例 2.5 addAtIndex(在第n个节点前插入节点)2.5.1 思路分析2.5.2 代码示例 2.6 deleteAtIndex(删除第n个节点的节点)2.6.1 思路分析2.6.2 代码示例 3. 代码汇总 1. 算法分析
【题目链接】 LeetCode 707 设计链表
这是一道很经典的题涵盖了链表的常见基本操作包括
获取第n个节点的值头部插入节点尾部插入节点在第n个节点前插入节点删除第n个节点的节点
注下述解题过程中使用到了虚拟头节点的方式进行操作最开始都是从虚拟头节点开始遍历的并且在单链表每次寻找节点都只找到目标节点的前一个节点这样可以方便我们对目标节点进行操作
2. 解题过程
2.1 初始化
2.1.1 思路分析 最开始需要先定义好Node节点类包括变量val(节点值) 和 next(当前节点的下一个节点)并设置对应的构造方法方便我们后续创建节点时能够直接赋值 创建MyLinkedList的构造方法用来初始化 虚拟头节点head 和 链表长度 size 2.1.2 代码示例
class Node {int val;Node next;public Node(){}public Node(int val) {this.val val;}public Node(int val, Node next) {this.val val;this.next next;}
}class MyLinkedList {Node head;int size;public MyLinkedList() {this.head new Node();size 0;}...
}之后编写对应的每个方法
2.2 get(获取第n个节点的值)
2.2.1 思路分析 当 index 大于 链表长度时返回-1 定义count用来表示当前cur所处位置注cur是从虚拟头节点开始遍历的当count 0时 cur 正在头节点上 进入循环当 cur ! null cur.next ! null 时进行判断 当 count index 时表示当前 cur 的下一个节点就是目标节点 返回 cur.next.val 即可 当 count ! index 时cur 继续往下遍历即 cur cur.next; 判断结束后 无论结果 count 都要 1重复上述过程直到返回结果 2.2.2 代码示例
public int get(int index) {if (index size) {return -1;}Node cur head;int count 0;while (cur ! null cur.next ! null) {if (count index) {return cur.next.val;}cur cur.next;}return -1;
}2.3 addAtHead(头部插入节点)
2.3.1 思路分析 构建 node 节点并传入参数 val 与 head.next使得 node节点的下一个节点 指向 当前头节点的下一个节点 之后让头节点的下一个节点指向 node节点同时链表长度 1; 2.3.2 代码示例
public void addAtHead(int val) {Node node new Node(val, head.next);head.next node;size;
}2.4 addAtTail(尾部插入节点)
2.4.1 思路分析 构建 cur 节点并指向头节点head后续通过cur进行遍历构建node节点并赋值val 进入循环当 cur.next ! null 时cur继续往下遍历直到 cur.next null表示当前cur已经是链表的最后一个节点了最后让 cur.next 指向 node节点 即可同时链表长度 1; 2.4.2 代码示例
public void addAtTail(int val) {Node cur head;Node node new Node(val);while (cur.next ! null) {cur cur.next;}cur.next node;size;
}2.5 addAtIndex(在第n个节点前插入节点)
2.5.1 思路分析 当 index 大于 链表长度时返回结果空 定义count用来表示当前cur所处位置注cur是从虚拟头节点开始遍历的当count 0时 cur 正在头节点上 进入循环当 cur ! null 时进行判断 当 count index 时表示当前 cur 的下一个位置就是目标插入位 构建node节点并传入参数 val 与 cur.nex t使得 node节点的下一个节点 指向 当前节点cur的下一个节点之后让 cur的下一个节点指向当前 node节点以此建立连接最后 链表长度 1返回结果空 当 count ! index 时cur 继续往下遍历即 cur cur.next; 2.5.2 代码示例
public void addAtIndex(int index, int val) {if (index size) {return;}int count 0;Node cur head;while (cur ! null) {if (count index) {Node node new Node(val, cur.next);cur.next node;size;return;}cur cur.next;}
}2.6 deleteAtIndex(删除第n个节点的节点)
2.6.1 思路分析 当 index 大于 链表长度时返回结果空 定义count用来表示当前cur所处位置注cur是从虚拟头节点开始遍历的当count 0时 cur 正在头节点上 进入循环当 cur ! null cur.next ! null 时进行判断 当 count index 时表示当前 cur 的下一个节点就是目标删除节点则让 cur 的下一个节点指向 cur 的下一个节点的下一个节点以此删除节点连接最后链表长度 - 1返回结果空; 当 count ! index 时cur 继续往下遍历即 cur cur.next; 2.6.2 代码示例
public void deleteAtIndex(int index) {if (index size) {return;}Node cur head;int count 0;while (cur ! null cur.next ! null) {if (count index) {cur.next cur.next.next;size--;return;}cur cur.next;}
}3. 代码汇总
class Node {int val;Node next;public Node(){}public Node(int val) {this.val val;}public Node(int val, Node next) {this.val val;this.next next;}
}class MyLinkedList {Node head;int size;public MyLinkedList() {this.head new Node();size 0;}public int get(int index) {if (index size) {return -1;}Node cur head;int count 0;while (cur ! null cur.next ! null) {if (count index) {return cur.next.val;}cur cur.next;}return -1;}public void addAtHead(int val) {Node node new Node(val, head.next);head.next node;size;}public void addAtTail(int val) {Node cur head;Node node new Node(val);while (cur.next ! null) {cur cur.next;}cur.next node;size;}public void addAtIndex(int index, int val) {if (index size) {return;}int count 0;Node cur head;while (cur ! null) {if (count index) {Node node new Node(val, cur.next);cur.next node;size;return;}cur cur.next;}}public void deleteAtIndex(int index) {if (index size) {return;}Node cur head;int count 0;while (cur ! null cur.next ! null) {if (count index) {cur.next cur.next.next;size--;return;}cur cur.next;}}
}以上便是对设计链表类型题的介绍了后续还会继续分享其它算法系列内容如果这些内容对大家有帮助的话请给一个三连关注吧( •̀ ω •́ )✧( •̀ ω •́ )✧✨
