链表专题
什么是链表？
链表是通过指针串联在一起的线性结构，每一个节点由两部分组成，一个数数据域，一个是指针域(存放指向下一个节点的指针)，最后一个节点的指针域指向null，空值。
分类：单链表，双链表，循环链表
单链表：
双链表
循环链表
时间复杂度：
链表的长度可以是不固定的，可以动态增删，适合数量不固定，频繁增删，较少查询的场景。在插入删除是时间复杂度是O(1)，在查询时是O(n)
怎样去写？
代码实现：
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; } }
链表操作的两种方式：
1.直接使用原来的链表进行操作
例如:在进行移除节点操作的时候，因为结点的移除都是通过前一个节点来进行移除的，那么我们应该怎么移除头结点呢，只需要将head头结点向后移动一格即可。
2.设置一个虚拟头结点进行操作
为了逻辑统一去移除节点，可以在head之前设置一个虚拟头结点，这样每个节点都可以通过相同的处理方式去移除了。
下面我们通过几个习题来进行练习和巩固基础吧！！！699
力扣题目专练
203. 移除链表元素
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
示例 1：
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]
示例 2：
输入：head = [], val = 1
输出：[]
示例3：
输入：head = [7,7,7,7], val = 7
输出：[]
提示：
列表中的节点数目在范围 [0, 104] 内
1 <= Node.val <= 50
0 <= val <= 50
思路：
我们使用带虚拟头，即上面的第二种方式来进行移除元素。思路很简单，可以参考一下代码：多敲几遍，增加熟练度
示例代码
/** * 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) { 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; } }
206. 反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例3：
输入：head = []
输出：[]
提示：
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000
思路：
如何将链表指向反过来，只需要将该节点的下一个指向该节点前一个节点即可，此时我们仍使用虚拟头结点，用一个while循环，当当前节点是空的时候，返回该节点前一个节点即可。原来的尾结点成了翻转后的头节点，所以可以正常打印出链表。
示例代码`
/** * 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 pre= null; ListNode cur= head; ListNode temp = null; while(cur!= null){ temp = cur.next; cur.next= pre; pre = cur; cur = temp; } return pre; } }
这两个题是最基础的链表入门题，相关的题目还有很多，建议多写几遍去理解一下实现过程和写法
