代码随想录算法训练营第三天| 203.移除链表元素 707.设计链表 206.反转链表

链表内容复习

* 链表的概念和结构
链表：链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接
次序实现的。（通俗的说：就是由一个个节点组成，这些节点逻辑上连续，物理上不连续）

将链表类比于火车：

singleLinkedList ——火车车次（一整个火车or哪趟火车）

Node——车厢，具体储存元素的类，每个单链表的节点就是Node的一个对象

Node.head ；——当前链表的头节点（只要知道头节点就可以此访问链表中的所有节点）

int size ；——当前链表的长度（节点个数），保存有效数据的个数

*
链表分为：单向链表、双向链表、循环链表

*
单向链表节点的定义(一定要会写，熟悉构造)
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;} }
* 链表的存储方式：
数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。

链表是通过指针域的指针链接在内存中各个节点。所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。

203.移除链表元素

给你一个链表的头节点 head和一个整数 val，请你删除链表中所有满足 Node.val == val的节点，并返回 新的头节点。
输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]
思路1：不使用虚拟节点，直接操作
class Solution { public ListNode removeElements(ListNode head, int val) {
//1.考虑头结点就是需要删除的值 while(head!=null&&head.val==val){ head=head.next; }
//2.列表为空的话，直接退出 if(head==null){ return head; } //3.已经确定了head.val!=val ListNode
pre=head; ListNode cur=head.next; while(cur!=null){ if(cur.val==val){
pre.next=cur.next; }else{ pre=cur; } cur=cur.next; } return head; } }
注意点：不适用虚拟头结点的话，需要注意判断head.val是否等于val。

思路2：使用虚拟头结点
class Solution { public ListNode removeElements(ListNode head, int val) {
if(head==null){ return head; } ListNode dummy=new ListNode(-1,head); ListNode
pre=dummy; ListNode cur=head; while(cur!=null){ if(cur.val==val){
pre.next=cur.next; }else{ pre=cur; } cur=cur.next; } return dummy.next; } }
两种思路效率差不多，但是使用虚拟头结点的话就不需要多余判断头结点的值是否等于val。

707. 设计链表

在链表类中实现这些功能：

* get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回1。
* addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
* addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
* addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val 的节点。如果 index
 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
* deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。 MyLinkedList
linkedList = new MyLinkedList(); linkedList.addAtHead(1);
linkedList.addAtTail(3); linkedList.addAtIndex(1,2); //链表变为1-> 2-> 3
linkedList.get(1); //返回2 linkedList.deleteAtIndex(1); //现在链表是1-> 3
linkedList.get(1); //返回3
单向链表
class MyLinkedList { public MyLinkedList() { int size=0; ListNode head=new
ListNode(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; } public void addAtHead(int val) { addAtIndex(0,val);
} public void addAtTail(int val) { addAtIndex(size,val); } public void
addAtIndex(int index, int val) { if(index>size){ return; } if(index<0){
index=0; } size++; //首先需要找到index之前的那个节点进行操作 ListNode pre=head; for(int
i=0;i<index;i++){ pre=pre.next; } //找到节点之后进行传入，需要新建一个节点add ListNode add=new
ListNode(val); add.next=pre.next; pre.next=add; } //如果索引 index 有效，则删除链表中的第
index 个节点。 public void deleteAtIndex(int index) { //首先判断index是否有效
if(index>=size||index<0){ return; } size--; if(index==0){ head=head.next;
return; } //找到需要删除的点的前一个 ListNode pre=head; for(int i=0;i<index;i++){
pre=pre.next; } pre.next=pre.next.next; } }
*
获取索引index处的值

利用for循环找到index处的链表，通过cur=cur.next; 循环结束后cur.val就是索引处的值

*
在index之前添加链表

和1类似，需要找到index-1处的节点进行添加处理

*
删除index节点处的链表

和1类似，结合203的移除元素

双向链表(只做了简单了解——后续需要结合实际题目，感觉目前用到的较少)

206.反转链表

给你单链表的头节点 head，请你反转链表，并返回反转后的链表。
输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1] 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; } }
链表的题重在理解，理解链表节点的走向，顺着理解去做题目就可以完成的很快速。

• « 上一篇：Mybatis-plus如何提前获取实体类用雪花算法生成的ID
• » 下一篇：git忽略本地文件的修改；撤销本地merge；撤销本地commit