【圣诞专场】刷完这套链表套题，面试官考链表的时候我笑出了声

⭐️引言⭐️
大家好，我是执梗，数据结构与算法的重要性相信大家都已经非常清楚。其中链表更是其中的重中之重，很多兄弟就感觉，诶无非单链表双链表实现增删改查，非常简单。确实，链表虽然简单，但许多兄弟也仅仅是在自己的编译器上完成过链表的这些基础功能。那如何检验自己的链表水平呢？——这里我为大家排好了一套链表专题，题目由简到难，囊括链表所有题型，帮你完美过渡。其中我也附带了自身的详细题解，照着这套题目刷下去，相信大家对于链表的操作更加是得心应手。建议收藏，有空时可根据题目顺序训练。

📒博客首页：执梗的博客

🎉欢迎关注🔎点赞👍收藏⭐️留言📝

❤️ ：热爱Java学习，期待一起交流！

🙏作者水平很有限，如果发现错误，求告知，多谢！

🌺有问题可私信交流！！！ ·

🍋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--;
    } 
}

🌿3.反转链表（简单但重要）

   给你单链表的头节点 

head

，请你反转链表，并返回反转后的链表。

   题目链接：反转链表 

   非常经典的题目，面试常考，人人都得必会的题！！        

    方法1**双指针迭代**：通过两个指针cur和pre，一次一次局部反转，遍历一次后完成全部反转。     

class Solution {
    public ListNode reverseList(ListNode head) {
        //cur在左  pre在右 
        ListNode pre=head;
        ListNode cur=null;
        while(pre!=null){
            //先保存住pre的next
            ListNode a=pre.next;
            pre.next=cur;
            cur=pre;
            pre=a;
        }
        return cur;
    }    
}

    方法2**递归**：这道题的递归比较抽象，需要大家自己动手演示一下流程才能想明白，但其实逻辑和双指针是一样的，建议还是掌握双指针方法即可。

class Solution {
    public ListNode reverseList(ListNode head) {
        //递归出口
        if (head == null || head.next == null) {
            return head;
        }
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

🌿4.两两交换链表中的节点（中等）

    给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

    题目链接：两两交换链表中的节点

    这道题的思路和上面很像，都是通过指针的思想，一定要去画图，这道题不画图一定会被搞混乱的，看while循环内的代码就能感觉到，再次印证了，**做链表题目一定要画图找出执行流程**。

cur设为虚拟头结点，为了统一操作，大家一定要养成设置虚拟头结点的习惯。

class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head==null) return head;
        //设置一个虚拟头结点
        ListNode dummyHead=new ListNode(-1,head);
        ListNode cur=dummyHead;
        while(cur.next!=null&&cur.next.next!=null){
            ListNode a=cur.next;
            ListNode b=cur.next.next.next;
            cur.next=cur.next.next;
            cur.next.next=a;
            cur.next.next.next=b;
            cur=cur.next.next;
        }
        return dummyHead.next;
    }   
}

方法二递归：

这里的递归我刚开始也没理解，但是发现一篇很好的关于递归的博客——递归教学

class Solution {
    public ListNode swapPairs(ListNode head) {
          //终止条件：链表只剩一个节点或者没节点了，没得交换了。返回的是已经处理好的链表
        if(head == null || head.next == null){
            return head;
        }
          //一共三个节点:head, next, swapPairs(next.next)
          //下面的任务便是交换这3个节点中的前两个节点
        ListNode next = head.next;
        head.next = swapPairs(next.next);
        next.next = head;
          //根据第二步：返回给上一级的是当前已经完成交换后，即处理好了的链表部分
        return next;
    }
}

🌿5.删除链表倒数第N个节点（中等）

    给你一个链表，删除链表的倒数第 

n

• *个结点，并且返回链表的头结点。

    题目链接：删除链表倒数第N个节点
  
    同样是非常经典的题目，解法也有很多，最基础最重要的还是利用快慢双指针加虚拟头节点。大家一定要在反复练习，多看题解区的题解，化他人的知识为自己所用。
  

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //快慢指针方法
        //定义虚拟头结点
        ListNode dummyHead=new ListNode(-1,head);
        //定义快慢指针，慢指针负责找到待删除节点的前一个节点
        ListNode show=dummyHead;
        ListNode fast=dummyHead;
        //让fast先走n+1格，当fast走完时刚好show指向倒数第n+1个
        for(int i=1;i<=n+1;i++){
            fast=fast.next;
        }
        while(fast!=null){
            fast=fast.next;
            show=show.next;
        }
        //删除show指向的下一个节点
        show.next=show.next.next;
        return dummyHead.next;
    }
}

🌿6.链表相交（面试题）

    给你两个单链表的头节点 

headA

和

headB

，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回

null

。

    题目链接：链表相交

    这道题在LeetCode被判断为简单题，但是却有一点难度，很多容易被人忽视的小细节，如判断相等时我们应该判断的是节点相等而不是节点的val相等。这里通过长度差，让长短不一的两条链表在末尾对齐的情况下，从同一长度开始遍历，如果有相等的时候直接返回即可，遍历完仍未找到返回null。        

方法1：求出长度差统一起始点来遍历判断。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
           //求出长度差值进行判断
           int countA=0;
           int countB=0;
           ListNode a=headA;
           ListNode b=headB;
           //求a链表的长度
           while(a!=null){
               countA++;
               a=a.next;
           }
           //求b链表的长度
           while(b!=null){
               countB++;
               b=b.next;
           }
           //重置a，b
           a=headA;
           b=headB;
           //如果B更长就交换它们
           if(countB>countA){
               int temlen=countA;
               countA=countB;
               countB=temlen;
               ListNode temNode=a;
               a=b;
               b=temNode;
           }
           //求长度差
           int x=countA-countB;
           //让a和b同一起跑线（末尾对齐）
           while(x-->0){
               a=a.next;
           }
           //同时遍历a和b，遇到相同则返回
           while(a!=null){
               //是a==b而不是a.var==b.var
               if(a==b) return a;
               a=a.next;
               b=b.next;
           }
           //没找到返回Null
           return null;
    }
}

方法2：我们知道，A和B链表长度可能是不等的，但链表A+B和B+A的长度却是相等的。如果A和B的结尾具有相同的节点，那么A+B和B+A也会有相同的，这样我们就能克服长度不同的困难。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a=headA;
        ListNode b=headB;
        //a==b时要么找到了相等，要么两者同时遍历完都为null（都为null时也是相等的情况，所以不会死循环，因为遍历的长度都相等，所以最后没找到相同的情况下，它们会最后同时为null）
        while(a!=b){
            //如果A遍历完则接着遍历B
            a=a!=null?a.next:headB;
            //如果B遍历完则接着遍历A
            b=b!=null?b.next:headA;
        }
        //这里a或b都可以。当二者都为null出来说明没有相同的节点，否则就是找到了相同节点
        return a;
    }
}

🌿7.环形链表（简单）

    给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。

题目链接：环形链表

方法1：利用HashSet存储遍历过的节点，如果判断到已存储过返回直接返回true，遍历完的话返回false（时间复杂度O（N），空间复杂度O（N））

public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> set=new HashSet<ListNode>();
        ListNode a=head;
        while(a!=null){
            if(!set.contains(a)){
                set.add(a);
            }else{
                //说明回到了环起点，有环
                return true;
            }
            a=a.next;
        }
        //遍历完无重复节点，无环
        return false;
    }
}

方法2龟兔赛跑：其实也是快慢双指针方法，如果链表成环，快指针肯定会因为速度比慢指针快从而超过慢指针一圈而赶上慢指针。如果快指针跑到终点为接近null，说明这个链表就无环。

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null||head.next==null) return false;
        //快指针需要在慢指针右边，这样才会进入下面while循环体
        ListNode slow=head;
        ListNode fast=head.next;
        while(slow!=fast){
            //如果fast后面即将为null说明到了链表尾部返回false，链表无环
             if(fast==null||fast.next==null) return false;
             fast=fast.next.next;
             slow=slow.next;           
        }
        //跳出循环了说明slow==fast，快指针追上了慢指针，链表有环
        return true;
    }
}

🌿8.环形链表||（中等）

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改链表。

题目链接：环形链表||

与上一题类型，只不过返回值不一样了，所以大部分方法是通用的。

方法1：同理与上一题的方法1，用HashSet遍历，找到已存储过的节点就是环的起点，直接返回即可。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        Set<ListNode> set=new HashSet<ListNode>();
        ListNode a=head;
        while(a!=null){
            if(!set.contains(a)){
                set.add(a);
            }else{
                //已经存储过，说明这就是环起点
                return a;
            }
            a=a.next;
        }
        //遍历结束，说明无环
        return null;
    }
}

方法2双指针：同理于上一题的双指针思想，但这一题会有点难度，需要一定的数学归纳证明。同样第一次快慢指针相遇后可判断到有环。此时将快指针重置到head，然后和慢指针一样一次走一格，当他们二次相遇时，会在环的入口。这里贴上一篇数学归纳的证明链接：双指针法

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head==null||head.next==null) return null;
        ListNode slow=head;
        ListNode fast=head;
        while(true){
            //说明无环直接返回null
            if(fast==null||fast.next==null) return null;
            fast=fast.next.next;
            slow=slow.next;
            //第一次相遇
            if(slow==fast) break;
        }
        fast=head;
        while(fast!=slow){
            slow=slow.next;
            fast=fast.next;
        }
        return fast;
    }
}

🎨3.链表专题总结

   通过上面的题目其实我们很容易总结出一些做题的套路和技巧。**1.就是设置虚拟头结点。**因为在链表中头结点的处理往往比较特殊，通过设置虚拟头结点能帮助我们统一操作。**2.手动迭代过程**。链表类的题目最忌讳靠脑子去凭空想象，特别是初学阶段，自己演示流程，才能写出逻辑清晰的代码。**3.多搭配双指针算法。**通过上面的专题训练，可以很容易看出链表和双指针搭配的比重很大，所以做题时往往可以考虑双指针算法是否可行。**4.反复训练，多加练习**。这点也是最重要的，这套题大家可以反复训练加深印象，同时去力扣寻找更多的链表题目进行训练。相信有了这套专题，以后面试一定能手撕代码！

            **如果感到有用的兄弟们，麻烦三连支持一下！！！感谢**

文末小惊喜：

            ![](https://img-blog.csdnimg.cn/388d4b73fd934d358df8969311875e4e.png)

Java学习路线总结，搬砖工逆袭Java架构师