• 【剑指offer&牛客101】中那些高频笔试，面试题——链表篇

    文章目录

    链表类

    牛客101

    1. 反转链表

    题目链接：反转链表

    题目描述：

    在这里插入图片描述

    解题思路：

    在这里插入图片描述

    代码实现：

    /*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        // 方法一迭代
        // 设置两个指针 prv 和 cur
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null) {
            ListNode next = cur.next;//保存cur的下一个节点
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    2. 链表内指定区间反转

    题目链接：链表内指定区间反转

    题目描述：

    在这里插入图片描述

    解题思路：

    前一道题，我们知道如何去反转一个链表，这道题，指定区间反转，意思就是 对给出的区间的链表，进行反转，那么，我把这道题进行分解：

    1. 首先找到 m 和 n 的位置
    2. 将 m 和 n 分离出来
    3. 最后在将链表拼接起来即可

    代码如下

    import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param m int整型 
     * @param n int整型 
     * @return ListNode类
     */
    public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        // 设置虚拟节点
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;
        // 让pre 走到 m的前一个节点
        for(int i = 0;i < m-1;i++) {
            pre = pre.next;
        }
        // 找到n节点,让rightNode 走到 n的节点
        ListNode rightNode = pre;
        for(int i = 0;i < n-m+1;i++) {
            rightNode = rightNode.next;
        }
        // 取出出子链
        ListNode leftNode = pre.next;
        ListNode cur = rightNode.next;
        // 截断子链
        pre.next = null;
        rightNode.next = null;
        // 反转子链
        reverseNode(leftNode);
        // 拼接子链
        pre.next = rightNode;
        leftNode.next = cur;
        return dummyNode.next;// 返回头结点
    }
    public void reverseNode(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57

    3. 从尾到头打印链表

    题目链接： 从尾到头打印链表

    题目描述：

    在这里插入图片描述

    解题思路：

    这道题有两个方法：

    1. 方法一：也是我们最能常想到的，用栈
    2. 方法二：借用力扣大佬一思路：不用栈，不用递归，不额外分配空间

    代码如下：

    /** 方法一：
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        Stack<Integer> stack = new Stack<>();
        // 用栈来做,先遍历链表，将val放入栈中
        ListNode cur = head;
        while(cur != null) {
            stack.push(cur.val);
            cur = cur.next;
        }
        // 创建个数组，数组大小为栈的大小
        int size = stack.size();
        int[] nums = new int[size];
        // 遍历数组，给数组赋值
        for(int i = 0;i<size;i++) {
            nums[i] = stack.pop();
        }
        return nums;
    }
}


/** 方法二：
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        ListNode cur = head;
        // 先遍历看看到底有多少个节点
        int count = 0;
        while(cur != null) {
            count++;
            cur = cur.next;
        }
        int[] nums = new int[count];
        cur = head;// 这里让cur指向头节点
        // 从后往前打印
        for(int i = count -1;i >=0;i--) {
            nums[i] = cur.val;
            cur = cur.next;
        }
        return nums;

    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57

    4. 复杂链表的复制

    题目链接：复杂链表的复制

    题目描述：

    在这里插入图片描述

    解题思路：

    遇到题，不要慌，先把题目分析一遍，就是说：复制一个新的链表出来，那么我们需要分析拆解问题：

    1. 新的链表的每个节点的val值不变
    2. 新的链表的next和random指针需要我们去修改
    3. 用什么方法最好？采用哈希，做映射 key-value 对应 原节点-新节点

    两个循环，第一个循环建立 key-value 映射关系（原节点val和新节点val）
    第二个循环，根据映射关系，修改新节点的next和random指针

    代码如下：

    // 方法二：
class Solution {
    public Node copyRandomList(Node head) {
        Map<Node,Node> map  = new HashMap<>();
        Node cur = head;//cur 代替 头结点 去遍历
        //1.第一次遍历 将老节点和新节点的映射关系放入map中
        while(cur != null) {
            //复制 节点 为 新节点
            Node node = new Node(cur.val);
            //存储 老节点 和新节点的 映射关系
            map.put(cur,node);
            cur = cur.next;
        }
        //第二次遍历 先让cur 指向头结点
        cur = head;
        //第二次遍历 修改新节点的 next 和 random指向
        while(cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        //最后返回 新的头节点
        return map.get(head);
        
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26

    5. 链表中的节点每K个一组翻转

    题目链接：链表中的节点每K个一组翻转

    题目描述：

    在这里插入图片描述

    解题思路：

    这道题，题目描述的很清楚，思路很简单，但是对于代码上来说，需要一定的要求，这里我借用力扣一大佬的图解，给大家分析。
    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    代码如下：

    
import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    // 递归法
    public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        // 先判断递归终止条件
        if(head == null || head.next == null) {
            return head;// 如果没有头节点为空，或者只有一个节点
        }
        ListNode tail = head;
        // 让tail 走 k-1 步
        for(int i = 0;i < k;i ++) {
            // 这里需要注意：如果剩余的数量小于k了，则不需要翻转
            if(tail == null) {
                return head;
            }
            tail = tail.next;
        }
        
        // 翻转钱K个节点 注意这里的范围为：[);
        ListNode newHead = reverse(head,tail);
        // 递归，下一次开始的其实位置是tail
        head.next = reverseKGroup(tail,k);
        return newHead;
    
    }
    
    public ListNode reverse(ListNode head,ListNode tail) {
        // 翻转链表
        ListNode pre = null;
        ListNode next = null;
        while(head != tail) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56

    剑指 offer

    6.剑指 Offer 18. 删除链表的节点

    题目链接：删除链表的节点

    题目描述：

    在这里插入图片描述

    解题思路：

    核心思路：先读懂题意，要让我们删除节点，如何删除节点？首先，找到节点，找到节点之后，改变此节点的前后指向，即可完成删除，下面代码含详细注释

    代码实现：

    /**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        //删除节点 首先找到节点
        // 1. 先判断头节点，如果头刚好就是，那么返回头结点下一个节点
        if(head.val == val) return head.next;
        // 2. 设置两个指针
        ListNode pre = null;
        ListNode cur = head;
        // 3. 进入循环，先找到 要删除的节点
        // 这里的循环条件，如果 找到了就跳出循环，没找到，当cur遍历到最后的时候，退出循环
        while(cur != null && cur.val != val) {
            pre = cur;
            cur = cur.next;
        }
        // 跳出循环,如果cur不等于空，说明cur.val == val
        if(cur != null) {
            pre.next = cur.next;
        }
        // 最后返回头结点
        return head;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30

    7.剑指 Offer 22. 链表中倒数第k个节点

    题目链接：链表中倒数第k个节点

    题目描述：

    在这里插入图片描述

    解题思路：

    这道题，我一开始做的时候，我的想法是，反转两次链表，第一次反转链表之后，在去遍历1-k，遍历完成之后，再次反转，但是写了一半，考虑到时间复杂度的问题，没写了哈哈，接下来我们说说这道题的正确的核心思路把。这道题的核心思路如下：

    先读懂题意，题目上说，输出链表的倒数第K个节点，那么具体的方法很简单

    在这里插入图片描述

    这道题，我觉得能做出来，还得是一种经验，刷过这种类似的自然而然就能联想到一些方法。

    • 设置 快慢指针 fast 和 slow
    • fast 先走到 k+1 的位置，slow 从 head 位置开始，fast 和 slow 之间刚好就相差 k
    • 进入循环，fast 和 slow 同时一起走，当 fast == null 的时候，slow 的位置刚好就是 第 k 个节点
    • 最后 返回 slow 节点

    代码如下：

    /**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        // 核心思路：快慢指针（fast slow）先让 fast 走 k+1 步
        // slow 从第一个节点开始
        // 然后同时一起走，当 fast 走完 为 null 时，slow的位置就是
        // 倒数的位置

        // 快慢指针,并初始化
        ListNode fast = head;
        ListNode slow = head;

        // 先让 fast 走 k+1步
        // 注意：循环条件
        while(k > 0 && fast != null){
            fast = fast.next;
            k--;
        }

        // 然后 fast 和 slow 同时一起走
        // 当 fast 为 null 时 跳出循环
        while(fast != null) {
            fast = fast.next;
            slow = slow.next;
        }

        // 此时 头节点 为 slow 返回头节点 slow
            return slow;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    8.剑指 Offer 25. 合并两个排序的链表

    题目链接：合并两个排序的链表

    题目描述：

    在这里插入图片描述

    解题思路：

    先说一下我刚做这道题的思路体会，拿到这道题，读了遍题之后，我直接就开淦，想着，这简单嘛，直接 插入 嘛，1后面插1 在插2，在插3，再插4… ，这样子会出现个问题，先不说对不对，设置的引用就特别的多，贼蛋疼，后来还是选择老老实实的，重新做一遍，下面是核心思路：

    • 设置傀儡节点 和 引用 cur ，代替傀儡节点进行连接操作
    • 判断 两个链表的 val 值大小,来进行连接操作
    • 最后返回 头节点，dum.next

    注意 里面隐含了一个细节，A 链 和 B 链 可能长度不等，当跳出循环的时候，说明 其中一个链表 已经为空了，那么我们需要判断一下 到底是哪一个 为空 ，并且 将不为空的剩余部分 连接在 cur 的后面

    下面是具体代码，含注释，包懂！

    代码如下：

    /**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        // 核心思想，设置傀儡节点
        // 判断 l1.val 和 l2.val 的大小,在将他们连接在一起

        // 设置的傀儡节点
        ListNode dum = new ListNode(-1);
        // 用cur代替傀儡节点，进行连接
        ListNode cur = dum;
        // 进入循环，注意循环条件 当一个为null 的时候，跳出循环
        while(l1 != null && l2 != null) {
            // 进行判断
            if(l1.val <= l2.val) {
                cur.next = l1;
                l1 = l1.next;
            }else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        // 跳出循环,合并剩余的尾部：剩余尾部，那个剩下了，就将那个接在 cur.next 后面
        cur.next = l1 != null ? l1 : l2;
        return dum.next;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35

    9.剑指 Offer 52. 两个链表的第一个公共节点

    题目链接：两个链表的第一个公共节点

    题目描述：

    在这里插入图片描述

    解题思路：

    具体思路，在代码里面，我注释写的很详细，包懂

    代码如下：

    /**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 两个方法，如果去暴力遍历的话  复杂度就 大于 0（N）了
        // 肯定是不行
        // 核心思路：我们分析这个图，首先 A 的长度 和 B 的长度是不相同的！
        // 但是 A + B 的总长度 是相同的，我们利用这个性质（可以画个图），当 A 走完 走到 c3
        // A 就从 B 的头节点开始
        // 同理 当 B 走完 走到 c3 ，B 从 A 的头节点开始,因为 A 和 B 的长度不同，但是 A 和 B 的总数相同的性质
        // 在第二次遍历的时候 会相遇（画图好理解，这里我画图水平有限就不画了
        


        // 定义两个引用
        ListNode a = headA;
        ListNode b = headB;
        // 注意循环条件,当 a ！= b 的时候，循环的走下去
        while(a != b) {
            // 如果 A 走到 null 这个位置，就从 B 的头节点开始
            // 如果没有就继续走下去
            if(a == null) {
                a = headB;
            }else {
                a = a.next;
            }
            // 同理，如果 B 走到 null 这个位置，就从 A 的头节点开始
            if(b == null) {
                b = headA;
            }else {
                b = b.next;
            }
        }
        // 跳出循环，说明 a == b 了，返回 a 和 b 任意都可
        return a;   
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46

    🎉✨总结

    链表题，是笔试面试中的高频考点，难度不大，但是需要我们去熟练掌握，题型很多，有些题没做过，想真的很难想出来，所以一句话，熟能生巧，见多识广，多刷题多总结才是提升算法的做好途径

    “种一颗树最好的是十年前,其次就是现在”

    所以,

    “让我们一起努力吧,去奔赴更高更远的山海”

    如果有错误❌,欢迎指正哟😋

    🎉如果觉得收获满满,可以动动小手,点点赞👍,支持一下哟🎉

    以梦为马，不负韶华

    在这里插入图片描述

  • 相关阅读:
    Linux _gcc的学习
    每日三题 8.19
    MySQL之函数
    显卡、显卡驱动版本、cuda版本和Pytorch相互之间的依赖关系
    Flink整合kafka实现Flume监控指定文件改动
    前端日志采集方案浅析
    Docker 数据管理和网络通信
    .NET使用QuestPDF高效地生成PDF文档
    lnmp环境部署极简保姆级教程（nginx+php+mysql）
    CodeTON Round 6 (Div 1 + Div 2, Rated, Prizes!)(A - E)
  • 原文地址：https://blog.csdn.net/Biteht/article/details/125269195