当前位置 博文首页 > 文章内容

    三分恶的博客:LeetCode通关:听说链表是门槛,这就抬脚跨门而入

    作者:21344 栏目:未分类 时间:2021-11-25 22:21:52

    分门别类刷算法,坚持,进步!

    刷题路线参考:https://github.com/youngyangyang04/leetcode-master

          https://github.com/chefyuan/algorithm-base

    LeetCode通关:链表

    链表基础

    在开始刷题之前,我们最好先了解一下链表的一些基础知识,那么现在,我们开始吧。

    链表是一种链式存储的线性表,不要求逻辑上相邻的数据元素在物理位置上也相邻。

    单链表

    一个单向链表包含两个值: 当前节点的值和一个指向下一个节点的引用。也可以称之为数据域和指针域。

    入口节点称为头结点,最后一个节点指向null。

    如图所示:

    单链表

    双链表

    双链表,顾名思义,是有两个方向的链表。

    每个节点除了有指向下一个节点的引用,还有指向上一个节点的引用。

    双链表除了可以从前往后遍历,还可以从后往前遍历。

    双向链表

    循环链表

    循环链表,就是最后一个节点的后继指向头结点,头节点的前驱指向最后一个节点。

    循环链表

    链表的存储方式

    我们知道链表在内存中不是连续分配的。链表是通过指针域的指针链接内存中的各个节点。

    所以链表在内存中是散乱分布在内存中的某地址上,分配机制取决于操作系统的内存管理。

    链表内存分配

    链表的定义

    链表的定义主要包含两个部分:数据域指针域

    在Java中因为屏蔽了指针的存在,我们的定义可以是数据,后继/前驱节点。

    • 单链表:
     public class ListNode {
          int val;
          ListNode next;
          ListNode(int x) { val = x; }
      }
    
    • 双链表:
     public class ListNode {
          int val;
          ListNode prev;
          ListNode next;
          ListNode(int x) { val = x; }
      }
    

    链表基本操作

    我们以单链表为例,来看一下链表的一些基本操作:

    • 删除节点

    链表删除节点

    • 插入节点

    插入节点

    图中的插入和删除的时间复杂度都为O(1)。但是需要注意,这里的情况是插入和删除已经知道前趋节点的情况。

    如果,还需要检索相应的节点,那么时间复杂度是O(n)。

    链表操作

    LeetCode203. 移除链表元素

    ☕ 题目:203. 移除链表元素 (https://leetcode-cn.com/problems/remove-linked-list-elements/)

    ❓ 难度:简单

    📕 描述:给你一个链表的头节点 head 和一个整数 val ,请你删除链表中所有满足 Node.val == val 的节点,并返回 新的头节点

    题目示例

    💡 思路:

    删除链表节点,需要分为两种情况:

    • 删除节点是头结点:我们将头结点指向头结点的下一个节点

    头结点

    • 删除节点是非头结点:我们需要将当前节点的前一个节点指向当前节点的下一个节点

    非头结点

    我们来看一下代码实现:

       /**
         * @return cn.fighter3.linked_list.ListNode
         * @Description: 203. 移除链表元素
         * @author 三分恶
         * @date 2021/7/25 10:08
         */
        public ListNode removeElements(ListNode head, int val) {
            if (head == null) {
                return null;
            }
            ListNode cur = head;
            ListNode prev = head;
            while (cur != null) {
                ListNode temp = cur.next;
                //删除节点
                if (cur.val == val) {
                    //头节点
                    if (cur == head) {
                        head = temp;
                    }
                    //非头节点
                    if (cur != head) {
                        prev.next = cur.next;
                    }
                } else {
                    prev = cur;
                }
                cur = temp;
            }
            return head;
        }
    

    ⏰ 时间复杂度:O(n)。

    🏠 空间复杂度:O(1)。

    这道题,还有一个更巧妙一点的做法,就是虚拟头指针——虚拟头指针是链表算法题中非常好用的一个技巧。

    💡 思路:

    可以设置一个虚拟的头指针,让它的next指向头节点,这样头节点的删除就和普通节点是一致的了。

    虚拟头指针

    代码如下:

        /**
         * @return cn.fighter3.linked_list.ListNode
         * @Description: 203. 移除链表元素
         * @author 三分恶
         * @date 2021/7/25 10:08
         */
        public ListNode removeElements(ListNode head, int val) {
            if (head == null) {
                return null;
            }
            //虚拟头节点
            ListNode dummy = new ListNode(-1, head);
            ListNode prev = dummy;
            ListNode cur = head;
            while (cur != null) {
                if (cur.val == val) {
                    prev.next = cur.next;
                } else {
                    prev = cur;
                }
                cur = cur.next;
            }
            return dummy.next;
        }
    

    🚗 时间复杂度:O(n)。

    🏠 空间复杂度:O(1)。

    LeetCode707. 设计链表

    ☕ 题目:707. 设计链表 (https://leetcode-cn.com/problems/design-linked-list/)

    ❓ 难度:中等

    📕 描述:设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性:val 和 next。val 是当前节点的值,next 是指向下一个节点的指针/引用。如果要使用双向链表,则还需要一个属性 prev 以指示链表中的上一个节点。假设链表中的所有节点都是 0-index 的。

    在链表类中实现这些功能:

    • get(index):获取链表中第 index 个节点的值。如果索引无效,则返回-1。
    • addAtHead(val):在链表的第一个元素之前添加一个值为 val 的节点。插入后,新节点将成为链表的第一个节点
    • addAtTail(val):将值为 val 的节点追加到链表的最后一个元素。
    • addAtIndex(index,val):在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度,则该节点将附加到链表的末尾。如果 index 大于链表长度,则不会插入节点。如果index小于0,则在头部插入节点。
    • deleteAtIndex(index):如果索引 index 有效,则删除链表中的第 index 个节点。

    示例:

    MyLinkedList linkedList = new MyLinkedList();
    linkedList.addAtHead(1);
    linkedList.addAtTail(3);
    linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
    linkedList.get(1);            //返回2
    linkedList.deleteAtIndex(1);  //现在链表是1-> 3
    linkedList.get(1);            //返回3
    

    提示:

    • 所有val值都在 [1, 1000] 之内。
    • 操作次数将在 [1, 1000] 之内。
    • 请不要使用内置的 LinkedList 库。

    💡 思路:

    这是一道大题。

    链表基本操作的图示在前面已经给出了。

    比较简练的方式是设置一个伪头节点,保证链表永不为空,这样操作起来会方便很多。

    但是,我本人看过一点Java链表的代码,所以不想采用这种方式。

    PS:这里踩了一个坑,没仔细审题,链表index是从0开始的,导致思考5分钟,AC两小时。

    好了,我们直接看代码:

    /**
     * @Author: 三分恶
     * @Date: 2021/7/25
     * @Description: 707. 设计链表
     * https://leetcode-cn.com/problems/design-linked-list/
     * <p>
     * 链表界节点是 0——index
     **/
    
    public class MyLinkedList {
    
        //链表元素的个数
        int size;
        //头结点
        ListNode head;
    
    
        /**
         * 初始化链表
         */
        public MyLinkedList() {
            size = 0;
        }
    
        /**
         * 获取第index个节点的数值
         */
        public int get(int index) {
            //非法参数
            if (index < 0 || index >= size) {
                return -1;
            }
            ListNode cur = head;
            for (int i = 0; i < index; i++) {
                cur = cur.next;
            }
            return cur.val;
        }
    
        /**
         * 在链表最前面插入一个节点
         */
        public void addAtHead(int val) {
            addAtIndex(0, val);
        }
    
        /**
         * 在链表的最后插入一个节点
         */
        public void addAtTail(int val) {
            addAtIndex(size, val);
        }
    
        /**
         * 在第 index 个节点之前插入一个新节点,例如index为0,那么新插入的节点为链表的新头节点。
         * 如果 index 等于链表的长度,则说明是新插入的节点为链表的尾结点
         * 如果 index 大于链表的长度,则返回空
         */
        public void addAtIndex(int index, int val) {
            //非法参数
            if (index > size) {
                return;
            }
            if (index < 0) {
                index = 0;
            }
            //如果链表为空,直接作为头节点
            if (size == 0) {
                head = new ListNode(val);
                size++;
                return;
            }
            //插入
            size++;
            ListNode addNode = new ListNode(val);
            //插入头节点之前
            if (index == 0) {
                addNode.next = head;
                head = addNode;
                return;
            }
            //找到前驱节点
            ListNode pre = head;
            for (int i = 0; i < index - 1; i++) {
                pre = pre.next;
            }
            addNode.next = pre.next;
            pre.next = addNode;
        }
    
        /**
         * 删除第index个节点
         */
        public void deleteAtIndex(int index) {
            if (index < 0 || index > size-1) {
                return;
            }
            size--;
            //头节点
            if (index == 0) {
                head = head.next;
                return;
            }
            //非头节点
            ListNode prev = head;
            for (int i = 0; i < index - 1; i++) {
                prev = prev.next;
            }
            //删除节点
            prev.next = prev.next.next;
        }
    }
    

    ⏰时间复杂度:

    • addAtHead: O(1)
    • addAtInder,get,deleteAtIndex: O(n)。
    • addAtTail:O(n)。

    🏠空间复杂度:所有的操作都是 O(1)。

    虚拟头指针,以及双链表的实现,这里就留个白了。

    双指针解决的题目

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

    ☕ 题目:剑指 Offer 22. 链表中倒数第k个节点 (https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/)

    ❓ 难度:简单

    📕 描述:输入一个链表,输出该链表中倒数第k个节点。为了符合大多数人的习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。

    例如,一个链表有 6 个节点,从头节点开始,它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

    题目示例

    💡 思路:

    这道题可以用双指针的办法。

    以示例说明,一个指针pre在前,先跑1步,一个指针after在后,跟着跑,pre到头的时候,刚好afer是倒数第二个。

    倒数第k个节点

    代码实现:

        /**
         * 剑指 Offer 22. 链表中倒数第k个节点
         *
         * @param head
         * @param k
         * @return
         */
        public ListNode getKthFromEnd(ListNode head, int k) {
            if (head == null) {
                return null;
            }
            ListNode preNode = head, afterNode = head;
            int step = 0;
            while (preNode!=null) {
                preNode = preNode.next;
                step++;
                if (step > k) {
                    afterNode = afterNode.next;
                }
            }
            return afterNode;
        }
    

    ⏰ 时间复杂度:O(n)。

    LeetCode876. 链表的中间结点

    ☕ 题目:876. 链表的中间结点 (https://leetcode-cn.com/problems/middle-of-the-linked-list/)

    ❓ 难度:简单

    📕 描述:给定一个头结点为 head 的非空单链表,返回链表的中间结点。

    如果有两个中间结点,则返回第二个中间结点。

    示例

    💡 思路:

    和上一道题有点类似。

    上一道题是两个指针分先、后。

    这道题可以两个指针分快、慢。

    一示例1为例,fast指针跑两步,slow指针跑一步,fast指针恰好跑的是slow的两倍,fast指针跑到头了,slow指针不就恰好跑到中间了嘛!

    链表的中间节点

    代码如下:

        /**
         * 876. 链表的中间结点
         *
         * @param head
         * @return
         */
        public ListNode middleNode(ListNode head) {
            if (head == null) {
                return null;
            }
            //定义快慢指针
            ListNode fastNode = head, slowNode = head;
            while (fastNode != null && fastNode.next != null) {
                //快指针走两步
                fastNode = fastNode.next.next;
                //慢指针走一步
                slowNode = slowNode.next;
            }
            return slowNode;
        }
    

    ⏰ 时间复杂度:O(n)。

    LeetCode19. 删除链表的倒数第 N 个结点

    ☕ 题目:19. 删除链表的倒数第 N 个结点 (https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/)

    ❓ 难度:中等

    📕 描述:给你一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

    **进阶:**你能尝试使用一趟扫描实现吗?

    题目示例

    💡 思路:

    这道题上手是不是就觉得很熟?

    这是 203.移除链表元素 和 剑指 Offer 22. 链表中倒数第k个节点的结合。

    那么解法,我们同样可以结合这两道题。

    • 快慢指针找到倒数第N个节点
    • 虚拟头指针辅助删除

    删除倒数第N个节点

    代码如下:

      /**
         * @return cn.fighter3.linked_list.ListNode
         * @Description: 19. 删除链表的倒数第 N 个结点
         * @author 三分恶
         * @date 2021/7/25 17:17
         */
        public ListNode removeNthFromEnd(ListNode head, int n) {
            if (head == null) {
                return null;
            }
            //快慢指针
            ListNode fast = head, slow = head;
            //虚拟头节点
            ListNode dummy = new ListNode(-1);
            dummy.next = head;
            //一个指针从虚拟头节点开始跑
            ListNode preSlow = dummy;
            //计算步数
            int step = 0;
            while (fast != null) {
                //fast先走n步
                fast = fast.next;
                step++;
                //slow开始移动
                if (step > n) {
                    slow = slow.next;
                    preSlow = preSlow.next;
                }
            }
            //找到倒数第n个节点,和它的前驱
            preSlow.next = slow.next;
            return dummy.next;
        }
    

    ⏰ 时间复杂度:O(n)。

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

    ☕ 题目:876. 链表的中间结点 (https://leetcode-cn.com/problems/middle-of-the-linked-list/)

    ❓ 难度:简单

    📕 描述:给定一个头结点为 head 的非空单链表,返回链表的中间结点。

    如果有两个中间结点,则返回第二个中间结点。

    题目示例

    💡 思路:

    他们都说这道题浪漫,我却不想听什么狗屁的浪漫爱情故事,我只想搞钱。

    这道题可以用双指针解决,定义两个指针,当某一指针遍历完链表之后,然后掉头去另一个链表的头部,继续遍历。因为速度相同所以他们第二次遍历的时候肯定会相遇。

    如图(来自参考[3]):

    图片来自参考[3]

    代码实现:

        /**
         * 剑指 Offer 52. 两个链表的第一个公共节点
         *
         * @param headA
         * @param headB
         * @return
         */
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) {
                return null;
            }
            //定义两个节点
            ListNode nodeA = headA, nodeB = headB;
            while (nodeA != nodeB) {
                //没到头就后移,到头,就指向另一树头结点
                if (nodeA != null) {
                    nodeA = nodeA.next;
                } else {
                    nodeA = headB;
                }
                //另一个节点也一样
                if (nodeB != null) {
                    nodeB = nodeB.next;
                } else {
                    nodeB = headA;
                }
            }
            return nodeA;
        }
    

    ⏰ 时间复杂度:O(m+n),m和n分别为两个链表的长度。

    160. 相交链表 、面试题 02.07. 链表相交 和这道题基本是一模一样的。

    LeetCode206. 反转链表

    ☕ 题目:206. 反转链表 (https://leetcode-cn.com/problems/reverse-linked-list/)

    ❓ 难度:简单

    📕 描述:给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。

    题目示例

    💡 思路:

    这是一道非常经典的题目。翻转怎么做呢?

    遍历链表,将当前节点的后继指向当前。

    反转链表

    在这里我们要额外引入两个指针:

    • 一个prev表示前趋,用于反转时候后继的指向。
    • 一个temp用于临时存储下一个节点,这个temp是用来干什么的?用来遍历,因为反转之后,原来的next节点已经指向prev了。

    说真的,作为一个C语言菜鸡,我又想起了被指针数组、数组指针支配的日子,所以我画了一个作为Java程序员理解的示意图,如有不当之处,请指出。

    反转链表

    也找到了一张动图(参考[1]):

    在这里插入图片描述

    代码如下:

        /**
         * 206. 反转链表
         *
         * @param head
         * @return
         */
        public ListNode reverseList(ListNode head) {
            ListNode prev = null;
            ListNode current = head;
            while (current != null) {
                //保存下一个节点
                ListNode temp = current.next;
                //修改当前节点后继指向
                current.next = prev;
                //修改前趋节点
                prev = current;
                current = temp;
            }
            return prev;
        }
    

    ⏰ 时间复杂度:O(n)。

    LeetCode92. 反转链表 II

    ☕ 题目:92. 反转链表 II (https://leetcode-cn.com/problems/reverse-linked-list-ii/)

    ❓ 难度:中等

    📕 描述:给你单链表的头指针 head 和两个整数 left 和 right ,其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点,返回 反转后的链表 。

    题目示例

    💡 思路:

    反转链表经常容易忘,我们再做一道进阶的题目来巩固一下。

    这道题什么思路呢?

    我们可以把反转的这一部分拆出来,作为新的链表,反转新链表,然后再和前后的节点重新连接。

    反转链表-II

    代码实现:

       /**
         * @return ListNode
         * @Description: 92. 反转链表 II
         * @author 三分恶
         * @date 2021/7/24 0:32
         */
        public ListNode reverseBetween(ListNode head, int left, int right) {
            //虚拟头节点
            ListNode dummy = new ListNode(-1);
            dummy.next = head;
            ListNode cur = dummy;
            //一、获取被截取的子链表的前、后节点
            //移动到左节点前一个节点
            int i = 0;
            for (; i < left - 1; i++) {
                cur = cur.next;
            }
            //保存左节点的前一个节点
            ListNode leftPre = cur;
            //移动到right节点
            for (; i < right; i++) {
                cur = cur.next;
            }
            //保存右节点的后一个节点
            ListNode rightAfter = cur.next;
            //二、截取子链表
            //切断右节点后的部分
            cur.next = null;
            //左节点作为子链表头节点
            ListNode sonHead = leftPre.next;
            //切断左节点前的部分
            leftPre.next = null;
            //三、反转子链表
            ListNode rNode = reverseList(sonHead);
            //四:重新连接
            leftPre.next = rNode;
            sonHead.next = rightAfter;
            return dummy.next;
        }
    
        /**
         * @return ListNode
         * @Description: 反转链表
         * @author 三分恶
         * @date 2021/7/25 10:06
         */
        ListNode reverseList(ListNode head) {
            ListNode prev = null;
            ListNode cur = head;
            while (cur != null) {
                ListNode temp = cur.next;
                cur.next = prev;
                prev = cur;
                cur = temp;
            }
            return prev;
        }
    

    ⏰ 时间复杂度:O(n)。

    LeetCode234. 回文链表

    ☕ 题目:234. 回文链表(https://leetcode-cn.com/problems/palindrome-linked-list/)

    ❓ 难度:简单

    📕 描述:请判断一个链表是否为回文链表。

    题目示例

    💡 思路:

    要是双向链表就好了,直接一个指针从头到尾,一个指针从尾到头,但是这是一个单链表。

    所以我们可以用一个列表先把之给存起来,再用双指针分别从两头遍历比较。

    代码如下:

        /**
         * 234. 回文链表
         * 将值复制到集合
         *
         * @param head
         * @return
         */
        public boolean isPalindrome(ListNode head) {
            if (head == null) {
                return false;
            }
            List<Integer> nodes = new ArrayList<>(16);
            //将链表的值放入集合
            while (head != null) {
                nodes.add(head.val);
                head = head.next;
            }
            //双向遍历集合
            int start = 0, end = nodes.size() - 1;
            while (start < end) {
                if (!nodes.get(start).equals(nodes.get(end))) {
                    return false;
                }
                start++;
                end--;
            }
            return true;
        }
    

    ⏰ 时间复杂度:O(n),其中 n 指的是链表的元素个数,。

    🏠 空间复杂度:O(n),其中 n 指的是链表的元素个数,因为我们用了一个ArrayList来存储数据。

    但是题目里还提出了一个进阶:

    你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题?

    既然空间复杂度O(1),那么就不能引入新的存储结构。

    还是上面那句话,要是双向链表就好了,我们就双向比较。

    所以,考虑一下,我们可以把链表的后半段翻转一下,然后再比较。

    回文链表

    为了完成这个目的,大概需要分三步:

    • 找到中间结点
    • 翻转链表后半段
    • 前半段和后半段比较

    所以这种做法就是 876. 链表的中间结点 和 206. 反转链表 的组合。

    代码实现如下:

        /**
         * 234. 回文链表
         * 快慢指针法
         *
         * @param head
         * @return
         */