牛客网《BAT面试算法精品课》视频链接：《BAT面试算法精品课》 笔记链接： 牛客网《BAT面试算法精品课》笔记一：排序 牛客网《BAT面试算法精品课》笔记二：字符串 牛客网《BAT面试算法精品课》笔记三：队列和栈 牛客网《BAT面试算法精品课》笔记四：链表 牛客网《BAT面试算法精品课》笔记五：二分搜索 牛客网《BAT面试算法精品课》笔记六：二叉树 牛客网《BAT面试算法精品课》笔记七：位运算 牛客网《BAT面试算法精品课》笔记八：排列组合 牛客网《BAT面试算法精品课》笔记九：概率 牛客网《BAT面试算法精品课》笔记十：大数据 牛客网《BAT面试算法精品课》笔记十一：动态规划 1.链表问题算法难度不高，但考察代码实现能力 2.链表和数组都是一种线性结构 01数组是一段连续的存储空间 02链表空间不一定保证连续，为临时分配的 链表分类： 1按连接方向分类：单链表，双链表 2.按照有环无环分类：普通链表，循环链表 链表问题代码实现关键点： 01.链表调整函数的返回值类型，根据要求往往是节点类型 02.处理链表过程中，先采用画图的方式理清逻辑 03.链表问题对于边界条件讨论要求严格 关于链表插入和删除的注意事项 01.特殊处理链表为空，或者链表长度为1的情况 02.注意插入操作的调整过程 03.注意删除操作的调整过程 04.注意点：头尾结点及空节点需要特殊考虑 05.双链表的插入与删除和单链表类似，但是需要额外考虑previous指针的指向 单链表的翻转操作： 01.当链表为空或者长度为1时，特殊处理 单链表的翻转 注意点： 1.大量链表问题可以使用额外数据结构来简化调整过程 2.但链表问题最优解往往是不使用额外数据结构的方法 常见题型： 案例1： 给定一个整数num，如何在节点值有序地环形链表中插入一个节点值为num的节点，并且保证这个环形单链表依然有序。 时间按复杂度O(N)，额外空间复杂度O(1) 如果没地方插入，说明这个节点的值要么最大，要么最小 案例2. 给定一个链表中的节点node，但不给定整个链表的头结点。如何在链表中删除node？实现这个函数，要求时间复杂度为O(1)。 将节点2的值变成节点3的值，删除节点3 当要删除节点3时，这种方法就不行了，可以直接将3节点的值变为null 该删除方式并不是删除了该删除的节点，而是进行了值的拷贝 01.结构复杂拷贝操作受限时，不可行 02.在工程上会影响外部依赖 案例3. 给定一个链表的头结点head，再给定一个数num，请把链表调整成节点值小于num的节点都放在链表的左边，值等于num的节点都放在链表的中间，值大于num的节点，都放在链表的右边。 简单做法： 将链表的所有节点放入数组中，然后将数组进行快排划分的调整过程，然后将数组中的节点依次重新串连。 最优解是不需要任何的额外空间，只需要在遍历链表的时候把小于num的，等于num的，大于num的节点分别做成3个链表，最后连接起来就行了，比较考验代码实现能力。 案例4. 给定两个有序链表的有节点head1和head2，打印两个有序链表的公共部分 如果两个链表有一个为空，直接返回即可 如果都不为空，则C1,C2开始比较，刚开始c1为1，c2为2，c1<c2，c1往下移，c1为3，c1>c2，c2往下移，c2为3，c1=c2，输出3，继续执行….. 案例5. 如果链表为空，或者长度为1，或k<2，链表不用进行调整 方法一：时间复杂度O(N)，额外空间复杂度O(K) K个元素依次进栈，最后不够k个不进去 方法二：时间复杂度O(N)，额外空间复杂度O(1) 方法二与方法一类似，依然是每收集k个元素就做逆序，只是不用栈了 案例6. 给定一个单链表的头结点head，链表中每个节点保存一个整数，再给定一个值val，把所有等于val的节点删掉。 链表：7->1->3->1- >null 案例7. 判断一个链表是否为回文结构 例如： 链表1->2->3->2->1，是回文结构，返回true 链表1->2->3->1不是回文结构，返回false 方法一：时间复杂度O(N)，使用了N个额外空间 申请一个栈结构，入栈，然后出栈的时候与原来的链表比较，如果每一个节点值都与链表对应的值相等，那么返回true，否则返回false 方法二：时间复杂度O(N)，使用了N/2个额外空间 一个快指针每次走两步，一个慢指针每次走一步，满指针遍历时将遍历过的指针压入栈中，快指针走完的时候，慢指针会来到中间的位置，同时从栈顶到栈底的顺序其实是左部分的逆序，此时如果链表长度为奇数，就不把中间的节点压入栈中。 接下来慢指针继续遍历，栈也开始同步弹出节点，而且此时对比慢节点值和栈弹出节点的值是否相等，如果每一步都相等，那么返回true。 整个的算法相当于把链表的左半部分折过来与链表比较。 方法三：时间复杂度O(N)，额外空间复杂度O(1) 将右半部分链表翻转，然后依次首尾比较 案例8. 一个链表结构中，每个节点不仅含有一条指向下一个节点的next指针，同时含有一个rand指针，rand指针可能指向任何一个链表中的节点，请复制这种含有rand指针节点的链表。 案例9. 如何判断一个单链表是否有环？有环的话返回进入环的第一个节点，无环的话返回空。如果链表的长度为N，请做到时间复杂度O(N)，额外空间复杂度O(1). 普通解法利用哈利表来实现 最优解额外空间复杂度O(1)的方法： 快指针每次走两步，慢指针每次走一步，如果链表无环，快指针发现null后立即返回 如果链表有环，那么快指针和慢指针将在环中的某个位置相遇，在相遇的时刻，让快指针从头节点开始重新遍历，此时快指针每次走一步，满指针在环中也每次都走一步。当快指针和满指针再次相遇的时刻，相遇到的那个节点就是进入环的第一个节点。 案例10. 如何判断两个无环单链表是否相交？相交的话返回第一个相交的节点，不相交的话返回空，如果两个链表长度分别为N和M，请做到时间复杂度O(N+M)，额外空间复杂度O(1) 普通方法用哈希表来实现 最优解是遍历两个链表，统计他们的长度，比如一个链表长度100，一个50，我们让长度为100的链表先走50步，接下来两个链表再一起往下走，如果链表相交的话，那么他们在共同走的过程中一定会到达第一个相交的结点，如果一直到最后都没有相交，返回空 案例11. 如何判断两个有环单链表是否相交？相交的话返回第一个相交的节点，不相交的话返回空，如果两个链表长度分别为N和M，请做到时间复杂度O(N+M)，额外空间复杂度O(1) 入环节点是同一个节点情况1： 入环节点是同一个节点情况2： 入环节点不是同一个节点 案例12. 给定两个单链表的头结点head1和head2，如何判断两个链表是否相交？相交的话返回第一个相交的节点，不相交的话返回空。