链表五大必会--第二篇 适合新手

本来说昨天就要更第二篇的，结果晚上看了个电影。芬奇，可能随着年纪越来越大，这一步慢节奏公路旅行电影给我蛮多感受的，关于成长，关于自我，关于责任与坚持还有自己想要的生活是什么样子的。推荐大家在休闲的时候去看看。

顺便说一句

EDG 牛逼！

闲言少叙我们开始讲第二讲

这篇帖子算是自己的刷题笔记，写在地里分享给有需要的小伙伴。

问：什么是链表五大须会类别
答： 1. 单链表翻转题目  Leetcode 206, 92, 234
        2. 链表中环的检测  Leetcode 141, 142
        3. 两个有序链表的合并  Leetcode 160, 21, 23
        4. 删除链表倒数第n个节点
        5. 求链表的中间节点

在写链表的问题时注意内容：
a. 链表是否为空
b. 链表操作头或者尾是否能成功
（如果a, b同时存在，可实用一个哨兵节点dummy 来简化我们的程序）
c. 链表只有一个
d. 链表只有两个

关于哨兵节点：
主要是用于操作头节点和尾结点，统一处理
例如插入的时候 会有两种情况 list 为空 list不为空
例如删除的时候 会有两种情况 该节点不是最后节点，该节点是最后节点。

我们使用哨兵节点可以将其归并处理

关于链表的赋值连接的技巧
例如删除时  我们要先找到 cur.pre 和 后一位的关系 (类似于先找到小三，并且确立关系，在甩掉现任） 先找后一位在处理当前节点的过程，可以保证我们不会有遗漏或者溢出。（这个例子单纯是为了便于记忆）

正片开始
这篇帖子将讲述
第二部分 和 第三部分

关于第二部分链表有环的检测，最经典的Leetcode 题目是141 和 142
我们先来看 LeetCode 141 这道题
这道题没什么难的
策略就是快慢指针，快指针 但凡 比慢指针快那早晚就相遇。你想象一下你在操场跑圈。跑得快的同学早晚会在某一圈再次和跑的慢的同学再次相遇的
这道题就用到了上面提到的几个注意内容
1. 是否为空
2. 操作头尾是否能成功
3. 有一个entry能否成功
4. 有两个entry能否成功

这也就是为什么代码中要判断 fast != null && fast.next != null的原因

其它的没啥好说的 代码如下

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }
}

时间复杂度 O（n）空间复杂度 O（1）这道题 可以用Hashset 来写，但是会耗费额外的空间，就不赘述了大家有兴趣的可以去看一下高票答案

那么如何平滑的使用这个套路解答出follow up那？
我们来看142这题
142这道题和141基本一样。只不过这次从判断有没有环，上升到了那一位是环。
这道题卡了很久，卡主的原因是我没有想通其中的数学表达式。
我问了一下我的朋友，他在微软onsite的时候，遇到过这道题。当时8分钟秒了这道题，但是花了将近20分钟和面试官推到其中的数学公式，最终也是因为这一轮斩获了微软的offer。

那么废话不多说直接上图
variable如下所示
s: 起始点
f：环所在的位置
m：起始点到达环所在位置的长度
n：环以后每一圈的总长度
p：相遇点
x: 从环所在位置到达相遇点的距离
y: 从相遇点开始到达环所在位置的距离
k: k倍（跑了k圈遇到了slow）

我们通过推到得出这样一个公式
fast = 2 slow
(1)   k(跑了k圈）（n）+ y + m = 2(m + y)
(2)     m = kn - y
(3)     m = kn - n + x  (把y 替换成 x )
(4)  m = x + n(k - 1) 也就是说我们当k 为1 的时候 m = x  换句话讲 这时候head开始从起点出发，fast从相遇点出发 他们相遇的地方就是环所在的位置

那么话不多说上代码
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                // 这一步就是 m = x 的过程 让head 出发 遇到了 fast 就是环所在的位置
                while(head != fast){
                    head = head.next;
                    fast = fast.next;
                }
                return head;
            }
        }
        return null;
    }
}

时间复杂度 o（n） 空间 o(1)

参考内容
youtube 贾考博 传送门 https://www.youtube.com/watch?v=UkKBPGt5Nok&t=122s


第三部分有序表合并 对应题目 160， 21， 23
先来看160这道题
这道题如果单纯靠记忆过一段时间回来看就会忘记（我就是这样好一段时间）。理解他的原理就很简单了，大概来讲要明白pass by reference 这一个原理。
逻辑就是

• 没有相交点 a 走完 b 走完都到了null位置 返回0
• 有相交点
  

          a. 一样多的情况，a 走，b也走 走到相交的位置 返回

          b. 不一样多就有意思了，a走完的话 就让a 去走b 。 同理 b也做同样的事情，这样他们俩最后肯定会走相同数量的entry 早晚会知道遇到的点是谁

代码就很简单. 给新手的建议是，遇到这样简单代码的题，千万别去背，你要去讲原理。想象一下你要给一个没接触代码的人讲清楚其中逻辑。只要你能讲明白，基本上这题你就肯定会了。
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA, b = headB;
        while(a != b){
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }
        return a;
    }
}

时间复杂度o（n + m） n headA长度 m headB长度

接下来就是 21 Merge Two Sorted List 这道题
先说这道题的问题。就是标题意义，讲两个sorted list 合并起来
逻辑很简单，list1 的val < list2的val 就存list1 list1 = list1.next 反之亦然

这道题也是两种解法。

第一种解法 是针对这道题最优解
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        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;
        }


//主要是要注意这个部分，上面while循环是任意一个跑为空了，那就会停止，剩下的node就加在末尾就完了 这就要用下面这一行 给他们连起来
        cur.next = l1 == null ? l2 : l1;
        

        return dummy.next;
    }
}

时间复杂度 o(n + m) = o(n)  空间O(1)
第二种解法可以平滑到23 Merge K Sorted List 看你自己偏好吧 如果是面试遇到这道题，我猜follow up会是23 这样用第二种解法会帮助你节省一定的时间。
第二种解法使用了PQ来解决  有个问题就是 pq 时间复杂度的话是 o(nlogm)但是这道题的m只有2个 我在想 log以2底的2  不应该是1 吗 （我不太确定 有人知道答案可以分享一下）
pq有个神奇的地方就是在于能够在插入entry到q的时候帮我们排序大小，我们在把它pop出来就okay了

思路就是用pq 去装listNode 根据他们的val 来排序
骚操作来了，当我们取出一个queue的时候我们把第一个留下，剩下的在放回到queue里面在进行判断。

代码如下
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);

//特别注意因为比的是val 一定要先判断是不是为空
       if(l1 != null) pq.offer(l1);
        if(l2 != null) pq.offer(l2);
         while(!pq.isEmpty()){
            cur.next = pq.poll();
            cur = cur.next;
//我们留下第一位，把剩下的链表在丢回到pq里面，直到都走完为止 这样做的好处就是我们可以直接用这套模板去处理n个list的情况 平滑转移
            if(cur.next != null) pq.offer(cur.next);
        }
        return dummy.next;
    }
}

时间复杂度 o（nlogn） 空间复杂度o(n）

来到最后一题第23题
有了上一题的巨人的肩膀，这题简直是手拿把掐
23题就是如果有n个list的情况该怎么处理，这里的就不赘述了，简直是预判了他的预判！！！！！ 这波秀不秀！
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode dummy = new ListNode();
        ListNode cur = dummy;
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);

        for(ListNode list : lists){
       //还是记住我们pq里比的是val一定要判断是否为空
            if(list != null) pq.offer(list);
        }
        while(!pq.isEmpty()){
            cur.next = pq.poll();
            cur = cur.next;
            if(cur.next != null) pq.offer(cur.next);
        }
        return dummy.next;
    }
}

时间复杂度 o(nlogn) 空间复杂度 o（n）
当然这道题还有很多其它的解法。作为新手的我，因为掌握的数据结构和算法并不太多，更愿意在一个路径上去解决更多的问题。但是其实当我掌握了更多的数据结构和算法的时候确实是喜欢去讨论不同的解法，例如在学习DP算法的过程中，自顶向下 和 自底向上是两种解决思路，我每道题都争取两种方法都实验一下。但是，所以在这里，新手同学可以按着这个思路先把题熟悉起来，再去学习其他的解决方案也未尝不可。

我会尽快把后两个链表需会内容总结给大家，敬请期待~
顺便留个传送门 到 链表三部曲的第一部
https://www.1point3acres.com/bbs ... ;page=1#pid16250349






补充内容 (2021-11-09 23:07 +8:00):
最后两个必会类型实在是没什么好讲的大概看看就能明白  我更新一下题号把。如果任何人需要看代码的话，请在下方留言我会更新一片代码贴

4. 删除链表倒数第n个节点
            leetcode 237 103 19
5. 求链表的中间节点
            leetcode 876

顺便更新两道题到第一个类型
1. 单链表翻转题目  增加 24， 25两题

还不会链表，先Mark