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

特别感谢我的刷题小伙伴，昨晚不厌其烦的讲解和指导！感谢~

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

问：什么是链表五大须会类别
答： 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 和 后一位的关系 (类似于先找到小三，并且确立关系，在甩掉现任） 先找后一位在处理当前节点的过程，可以保证我们不会有遗漏或者溢出。

正片开始
第一类
单链表翻转题目。
看了个课程，某时间app里面的数据结构于算法。讲课人据说自己是google 前工程师，出席过上百场的面试。作为面试官的他说，每次出链表翻转，百分之八十多的面试者都写不出来。（反正我是不太信，随机在地里抓十个人，应该过半的人都能写出来206这题）

206 Reverse Linked List 题目要求就是翻转整个字符串。
我这里提供两个思路。
思路1 是可以解决关于从头到尾这样类似的问题的模板
代码如下
class Solution {
    public ListNode reverseList(ListNode head) {
        //record the final ans
        ListNode pre = null;
        //cur list
        ListNode cur = head;
        while(cur != null){
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}
具体图片如下所示

思路2 可以嵌套使用到 92 Reverse Linked List 2 当中 （平滑转移，丝滑享受）

代码如下
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode dummy = new ListNode();
        dummy.next = head;

//先计算有多少个翻转的数
        int count = 0;
        while(head != null){
            count ++;
            head = head.next;
        }

        ListNode pre = dummy;
        ListNode cur = pre.next;
//从1开始的原因是 翻转次数 =  翻转数 - 1
        for(int i = 1; i < count; i++){
            ListNode temp = cur.next;
            cur.next = temp.next;
            temp.next = pre.next;
            pre.next = temp;
        }
        return dummy.next;
    }
}

详情请看下图

Leetcode 92
中间一段翻转
这个题就能看出 单链表相比于双链表的劣势了。因为他无法储存前一位，所以我们需要先跑到翻转前一位记录一下。然后后面翻转n次

代码就很简单，沿用206 第二种思路来写就好

代码如下
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode();
        dummy.next = head;


        ListNode pre = dummy;
        for(int i = 0; i < left - 1; i++){
            pre = pre.next;
        }
        ListNode cur = pre.next;
        for(int i = left; i < right; i++){
            ListNode temp = cur.next;
            cur.next = temp.next;
            temp.next = pre.next;
            pre.next = temp;
        }
        return dummy.next;
    }
}

接下来是 234 Palindrom Linked List
这道题就是看是否是一个回文的linked list

思路：用快慢指针，快指针跑两位。翻转慢指针。比较快慢指针里的数 如果是不相同 那就gg

代码很简单

但是有个地方，卡了很久，最后在刷题小伙伴的帮助下想通的

Test Case [1,2,3,4,5]

class Solution {
    public boolean isPalindrome(ListNode head) {
        ListNode fast = head, slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        fast = head;
//在没跑 helper function时候  fast  【1,2,3,4,5】
        slow = helper(slow);
//跑完 helper function 之后 fast 【1,2,3】 我当时在想我的 4 5 被谁吃了！！！ （原因请看 后面图片）
        while(slow != null){
            if(slow.val != fast.val) return false;
            slow = slow.next;
            fast = fast.next;
        }
        return true;
    }
//翻转function
    public ListNode helper(ListNode shead){
        ListNode dummy = new ListNode();
        dummy.next = shead;
        int count = 0;
        while(shead != null){
            count ++;
            shead = shead.next;
        }
        ListNode pre = dummy;
        ListNode cur = pre.next;
        for(int i = 1; i < count; i++){
            ListNode temp = cur.next;
            cur.next = temp.next;
            temp.next = pre.next;
            pre.next = temp;
        }
        return dummy.next;
    }
}

原因是因为，我翻转3 4 5 ->null  导致了 我的fast 里面的链表断开了 从 1 2 3 -》 4 5 短开成 1 2 3-》null 了

突然发现码字比写码还费劲。关于第二条和第三天稍后更新。实在是累了

其实里面还有个问题也是想了很久，建议新手也要去了解一下 pass by reference  和 pass by value 的区别










补充内容 (2021-11-07 13:34 +8:00):
链表三部曲的第二篇  传送门  https://www.1point3acres.com/bbs/thread-816987-1-1.html

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

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

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

补充内容 (2021-11-19 01:49 +8:00):
更新一下题号
1. 单链表翻转题目  Leetcode 206, 92, 234, 25, 24
2. 链表中环的检测  Leetcode 141, 142
 3. 两个有序链表的合并和插入  Leetcode 160, 21, 23, 328, 2, 86, 445
 4. 删除链表倒数第n个节点LeetCode 82 83 237 203 19
 5. 求链表的中间节点leetcode 876
6. LRU 146
7. 扩展了解 138 148

额 文科生表示看到标题以为是楼主在讲七日链十日链腕表品牌挑选。我还是太嫩了

mark链表

代码用论坛自带的那个排版下

总结得很棒 谢谢分享

很棒谢谢分享！

马克链表。谢谢lz