🍋1.刷题须知与必备能力
首先这套题目，是建议在大家对链表有一定的了解和掌握的程度上来进行自我检验和训练的。不适合对链表没有了解的小白同学，如果对链表还是小白的同学，建议可以收藏文章日后阅读，同时为大家推荐观看我的链表文章：
单链表学习——单链表
双链表学习——双链表
做链表的题目有条件一定要在草稿纸上演示流程，不要凭空想象，这是大忌！！！
🍇2.有序刷题，循序渐进
🌿1.移除链表元素（简单）
给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
题目链接：移除链表元素
这道题比较基础，为了帮助大家入门，所以讲的比较细致。三种方法都希望大家自己手写一下并且理解掌握。
方法1：链表的定义本身带有递归性质，可以通过递归的方法求解。
class Solution { public ListNode removeElements(ListNode head, int val) { //递归出口 if (head == null) { return head; } //递归调用 head.next = removeElements(head.next, val); return head.val == val ? head.next : head; } }
方法2，3: 删除的时候，我们需要考虑一种情况，就是头结点是否是我们需要删除的节点，因为删除头结点的步骤和后面的节点会有所不同。这时我们可以设置一个虚拟的头结点放在真正的头结点前，这样就可以统一完成所有节点的删除步骤，当然也可以在将头结点单独来处理删除 ，这里我将两种代码都写出来了，供大家参考。
//有虚拟头结点的方法 class Solution { public ListNode removeElements(ListNode head, int val) { if(head==null) return head; //设置虚拟头结点a,next接上真正的头结点 ListNode a=new ListNode(-1,head); //b节点用来遍历链表 ListNode b=a; while(b.next!=null){ if(b.next.val==val){ b.next=b.next.next; }else{ b=b.next; } } //注意这里得写a.next不能写head return a.next; } }
//不设虚拟头结点 class Solution { public ListNode removeElements(ListNode head, int val) { //删除值相同的头结点后，可能新的头结点也值相等，用循环解决 while(head!=null&&head.val==val){ head=head.next; } if(head==null) return head; ListNode prev=head; //确保当前结点后还有结点 while(prev.next!=null){ if(prev.next.val==val){ prev.next=prev.next.next; }else{ prev=prev.next; } } return head; } }
🌿2.设计链表（中等）
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：val 和 next。val 是当前节点的值，next 是指向下一个节点的指针/引用。如果要使用双向链表，则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。
题目链接：设计链表
这道题能很好检验我们对链表的掌握能力，它需要我们实现指定的功能，大家一定要完成它。
class MyLinkedList { //虚拟头结点 Node head; //用来记录元素个数 int N; class Node{ int val; Node next; public Node(){} public Node(int val){ this.val=val; } } //构造方法 public MyLinkedList() { this.head=new Node(0); this.N=0; } //获取第index个节点的数值 public int get(int index) { //如果index非法，返回-1 if (index < 0 || index >= N) { return -1; } Node 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(N, val); } //完成制定插入 public void addAtIndex(int index, int val) { //非法直接返回 if(index>N){ return; } //index<0的情况和等于0是一样的 if(index<0){ index=0; } Node curr=head; //找到待插入位置的前一个节点 for(int i=0;i<index;i++){ curr=curr.next; } //完成插入操作 Node newNode=new Node(val); newNode.next=curr.next; curr.next=newNode; N++; } public void deleteAtIndex(int index) { //索引非法直接return if(index<0||index>=N) return; Node pre=head; //找到待插入的前一个节点 for(int i=0;i<index;i++){ pre=pre.next; } pre.next=pre.next.next; N--; } }
