分享｜2021秋招算法总结3-链表篇

- 掌握自定义ListNode的方法
- 掌握生成ListNode的方法（从int数组或者char数组转为ListNode）
- 掌握输出链表中每个节点的方法
- 提升：掌握LinkedList中常用的方法，学会用自带链表解决问题。PS：有些面试官要求只能用jdk自带类，具体可以看我写的腾讯客户端开发面经（21 届秋招），其中腾讯音乐二面的前三题就不让用自定义的链表。
- 提升：掌握常见List<*>和数组之间的转换方法。PS：用java的同学必备技能，因为实际面试时候如果给定输入输出类型，要会转换的方法。

以上在我的笔记中均有java版本，以下会截取一些重点的代码。其实方法有很多的，大家可以自行探索其他方法。

很多人有个疑问，链表学习时有多种不同办法怎么办，都要掌握么？个人建议：量力而行！学有余力的同学可以多看几种方法，然后记2-3种较好的即可；题目都看的云里雾里的同学就挑一个自己可以理解的方法记忆即可。再次戳重点：力扣题解区应有尽有，不要盲目相信市面上的总结（包括我的），而忽略了题解区大佬们的原创心血。

定义链表（java版本）

class ListNode{
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) {this.val = val;} //非必要，看自己需要的用法
    ListNode(int val, ListNode next) {this.val = val; this.next = next;} //非必要，看自己需要的用法
}

生成链表（java版本）

public static ListNode creat(int[] nums){
    ListNode pre = new ListNode(0), cur = pre;
    for (int num : nums){
        cur.next = new ListNode(num);
        cur = cur.next;
    }
    return pre.next;
}

输出链表（java版本）

方法1：常规法

public static void printList(ListNode head){
    while (head != null) {
        if (head.next != null) System.out.print(head.val + "->");
        else System.out.print(head.val);
        head = head.next;
    }
    System.out.println();
}

方法2：重写toString()

class ListNode{
     int val;
     ListNode next;
     ListNode(int val) { this.val = val; }
     @Override
     public String toString(){
        ListNode tmp = this;
        StringBuffer sb = new StringBuffer();
        while (tmp != null) {
            sb.append(tmp.val);
            if (tmp.next != null) {
                sb.append("->");
            }
            tmp = tmp.next;
        }
         return sb.toString();
     }
}

链表中的加法题

提示：不要因为简单而轻视这类题目，多思考边界条件及其变型！
1. 2. 两数相加：反向存放、反向输出。
2. 面试题 02.05. 链表求和：与上一题相比，有更多的边界条件。
3. 445. 两数相加 II：正向存放，正向输出。推荐看@sweetiee的简单Java

提升：尝试在本地编译器运行上述题目。

反转链表的题

注明：以下某些题目是可以用（但不限于用）反转链表思路的题目。
1. 206. 反转链表和剑指 Offer 24. 反转链表：一模一样的基础题，建议不懂反转链表套路的同学翻一翻这两题的题解区，找到对应语言的大佬们看看他们对此的解释（有画图很棒的大佬）。
2. 92. 反转链表 II：反转从位置m到n的链表。请使用一趟扫描完成反转。
3. 剑指 Offer 06. 从尾到头打印链表：输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
4. 143. 重排链表：不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
5. 25. K 个一组翻转链表：每k个节点一组进行翻转，返回翻转后的链表。PS：困难题看不懂的时候及时放弃。
6. 234. 回文链表和面试题 02.06. 回文链表：判断一个链表是否为回文链表。

相交链表的题

注明：这三题可以用同一个代码，大家可以自行揣摩题目的区别，反正代码是没啥区别。
1. 160. 相交链表
2. 剑指 Offer 52. 两个链表的第一个公共节点
3. 面试题 02.07. 链表相交

环形链表

1. 141. 环形链表：判断有没有环
2. 142. 环形链表 II：返回链表开始入环的第一个节点
3. 面试题 02.08. 环路检测：跟上题一样

倒数第k个节点

注明：都是用快慢指针法
1. 剑指 Offer 22. 链表中倒数第k个节点：返回的是节点
2. 面试题 02.02. 返回倒数第 k 个节点：返回的是节点的值（val）

提升：尝试用快慢指针法找单链表的中点。

删除链表中的某个节点

注明：注意题目之间的差异和边界条件。好几题的题目长的差不多，点进去以后略有不同。
1. 剑指 Offer 18. 删除链表的节点
2. 237. 删除链表中的节点和面试题 02.03. 删除中间节点
3. 19. 删除链表的倒数第N个节点
4. 83. 删除排序链表中的重复元素：给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
5. 82. 删除排序链表中的重复元素 II：给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中没有重复出现的数字。
6. 面试题 02.01. 移除重复节点：移除未排序链表中的重复节点。保留最开始出现的节点。
7. 203. 移除链表元素：删除链表中等于给定值val的所有节点。

排序链表

1. 147. 对链表进行插入排序：对链表进行插入排序。
2. 148. 排序链表：给你链表的头结点 head ，请将其按升序排列并返回排序后的链表。提升：如何输出按降序排列的链表。

合并链表

注明：第一题必会，后两题不会就算了吧，别纠结了。
1. 剑指 Offer 25. 合并两个排序的链表和21. 合并两个有序链表：输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
2. 1669. 合并两个链表：数字比较大的多半是竞赛题
3. 23. 合并K个升序链表：困难题，量力而行

分隔链表

注明：这是一个力扣迷惑现象：同名不同题，不同名同题。
1. 86. 分隔链表和面试题 02.04. 分割链表：给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
2. 725. 分隔链表：给定一个头结点为 root 的链表, 编写一个函数以将链表分隔为 k 个连续的部分。

结束语

链表的题目有点多，最常见的就是本文的题型，建议大家按类刷题，量力而行，先做那种可以双杀和三杀的题目，实在看不懂的某些中等或者困难题就跳过吧。