乐趣区

前端进阶面试链表不再怕

jiezi


观感度：????????????????????

口味：蒜蓉荷兰豆

烹饪工夫：8min

本文已收录在前端食堂同名仓库Github github.com/Geekhyt，欢迎光临食堂，如果感觉酒菜还算可口，赏个 Star 对食堂老板来说是莫大的激励。

链表

数组想必大家都很相熟，简直咱们每天都会操作它。那么咱们就来比照数组来学习链表，首先要明确的是，链表和数组的底层存储构造不同，数组要求存储在一块间断的内存中，而链表是通过指针将一组零散的内存块串联起来。可见链表对内存的要求升高了，然而随机拜访的性能就没有数组好了，须要 O(n) 的工夫复杂度。

下图中展现了单链表及单链表的增加和删除操作，其实链表操作的实质就是解决链表结点之间的指针。

在删除链表结点的操作中，咱们只须要将须要删除结点的前驱结点的 next 指针，指向其后继即可。这样，以后被删除的结点就被抛弃在内存中，期待着它的是被垃圾回收器革除。

为了更便于你了解，链表能够类比现实生活中的火车，火车的每节车厢就是链表的一个个结点。车厢之间相互连接，能够增加或者移除掉。春运时，客运量比拟大，列车个别会加挂车厢。

链表的结点构造由数据域和指针域组成，在 JavaScript 中，以嵌套的对象模式实现。

{
    // 数据域
    val: 1,
    // 指针域
    next: {
        val:2,
        next: ...
    }
}

名词科普

  • 头结点：头结点用来记录链表的基地址，是咱们遍历链表的终点
  • 尾结点：尾结点的指针不是指向下一个结点，而是指向一个空地址 NULL
  • 单链表：单链表是单向的，它的结点只有一个后继指针 next 指向前面的结点，尾结点指针指向空地址
  • 循环链表：循环链表的尾结点指针指向链表的头结点
  • 双向链表：双向链表反对两个方向，每个结点不止有一个后继指针 next 指向前面的结点，还有一个前驱指针 prev 指向后面的结点，双向链表会占用更多的内存，然而查找前驱节点的工夫复杂度是 O(1)，比单链表的插入和删除操作都更高效
  • 双向循环链表

循环链表

双向链表

双向循环链表

LeetCode 真题

把握了链表的基础知识后，咱们拿几道链表的 LeetCode 真题练练手，点击题目题目即可跳转到相干题目的形容页面。

1. 合并两个有序链表

思路

  • 应用递归来解题
  • 将两个链表头部较小的一个与剩下的元素合并
  • 当两条链表中的一条为空时终止递归

复杂度剖析

N+M 是两条链表的长度

  • 工夫复杂度：O(M+N)
  • 空间复杂度：O(M+N)
const mergeTwoLists = function (l1, l2) {if (l1 === null) {return l2;}
    if (l2 === null) {return l1;}
    if (l1.val < l2.val) {l1.next = mergeTwoLists(l1.next, l2);
        return l1;
    } else {l2.next = mergeTwoLists(l1, l2.next);
        return l2;
    }
};

2. 环形链表

思路

  • 双指针法
  • 应用快慢不同的两个指针遍历，快指针一次走两步，慢指针一次走一步
  • 如果没有环，快指针会先达到尾部，返回 false
  • 如果有环，则肯定会相遇

复杂度剖析

  • 工夫复杂度：O(N)
  • 空间复杂度：O(1)
const hasCycle = function(head) {if (!head || !head.next) {return false;}
    let fast = head.next;
    let slow = head;
    while (fast !== slow) {if (!fast || !fast.next) {return false;}
        fast = fast.next.next;
        slow = slow.next;
    }
    return true;
};

思路

  • 标记法
  • 遍历链表，通过标记判断是否有环，如果标记存在则有环。

复杂度剖析

  • 工夫复杂度：O(N)
  • 空间复杂度：O(1)
const hasCycle = function(head) {while (head) {if (head.flag) {return true;} else {
            head.flag = true;
            head = head.next;
        }
    }
    return false;
}

3. 反转链表

思路

  • 迭代
  • 初始化前驱节点为 null，初始化指标节点为头节点
  • 遍历链表，记录 next 节点并反转指针
  • prev 和 curr 指针别离往前挪动一步
  • 反转完结后，prev 成为新链表的头节点

复杂度剖析

  • 工夫复杂度：O(N)
  • 空间复杂度：O(1)
const reverseList = function(head) {
    let prev = null;
    let curr = head;
    while (curr !== null) {
        let next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
};

4. 删除结点的倒数第 N 个节点

思路

  • 删除倒数第 n 个结点，咱们须要找到倒数第 n+1 个结点，删除其后继结点即可
  • 增加 prev 结点，也称其为哨兵结点，解决边界问题
  • 应用双指针法，快指针先走 n+1 步，而后快慢指针同步往前走，直到 fast.next 为 null
  • 删除倒数第 n 个结点，返回 prev.next

复杂度剖析

  • 工夫复杂度：O(N)
  • 空间复杂度：O(1)
const removeNthFromEnd = function(head, n) {let prev = new ListNode(0);
    prev.next = head;
    let fast = prev;
    let slow = prev;
    while (n--) {fast = fast.next;}
    while (fast && fast.next) {
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;
    return prev.next;
};

5. 求链表的两头结点

思路

  • 双指针法
  • 应用快慢不同的两个指针遍历，快指针一次走两步，慢指针一次走一步
  • 当快指针达到起点时，慢指针刚好走到两头

复杂度剖析

  • 工夫复杂度：O(N) N 是给定链表的结点数目
  • 空间复杂度：O(1) 只须要常数空间寄存 slow 和 fast 两个指针
const middleNode = function(head) {
    let fast = head;
    let slow = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
};

❤️爱心三连击

1. 看到这里了就点个赞反对下吧，你的 赞是我创作的能源。

2. 关注公众号前端食堂，你的前端食堂，记得按时吃饭！

3. 本文已收录在前端食堂Github github.com/Geekhyt，求个小星星，感激 Star。

退出移动版