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

最大化缩小

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

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

本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
说我们IIS7站长博客，有一篇博文用了他们的图片。
要求我们给他们一张图片6000元。要不然法院告我们

为避免不必要的麻烦，IIS7站长博客，全站内容图片下架、并积极应诉
博文内容全部不再显示，请需要相关资讯的站长朋友到必应搜索。谢谢！

另祝：版权碰瓷诈骗团伙，早日弃暗投明。

相关新闻：借版权之名、行诈骗之实，周某因犯诈骗罪被判处有期徒刑十一年六个月

叹！百花齐放的时代,渐行渐远!

分门别类刷算法，坚持，进步！

刷题路线参考：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
     */



        
            
               
            
            
                
                    
                        立即下载 - IIS7 站长工具包

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

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

链表基础

单链表

双链表

循环链表

链表的存储方式

链表的定义

链表基本操作

链表操作

LeetCode203. 移除链表元素

LeetCode707. 设计链表

双指针解决的题目

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

LeetCode876. 链表的中间结点

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

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

LeetCode206. 反转链表

LeetCode92. 反转链表 II

LeetCode234. 回文链表

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