「前端进阶」面试链表不再怕

图怪兽_6d4a18670ef300724efa23b645349e9a_43640.png
观感度:🌟🌟🌟🌟🌟

口味:蒜蓉荷兰豆

烹饪时间:8min

链表

数组想必大家都很熟悉,几乎我们每天都会操作它。那么我们就来对比数组来学习链表,首先要明确的是,链表和数组的底层存储结构不同,数组要求存储在一块连续的内存中,而链表是通过指针将一组零散的内存块串联起来。可见链表对内存的要求降低了,但是随机访问的性能就没有数组好了,需要 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。

qrcode.jpg

以上是 「前端进阶」面试链表不再怕 的全部内容, 来源链接: utcz.com/a/31612.html

回到顶部