数据结构（四）链表

最后更新时间：2021年10月20日

链表是什么？

  • 多个元素组成的列表
  • 元素存储不连续，用next指针连在一起

数组 VS 链表

  • 数组：增删非首尾元素时往往需要移动元素
  • 链表：增删非首尾元素，不需要移动元素，只需要更改next指向即可

JS中的链表

  • JavaScript中没有链表
  • 可以用Object模拟链表

Coding Part

LeetCode #237 删除链表中的节点

请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点。传入函数的唯一参数为 要被删除的节点 。

现有一个链表 -- head = [4,5,1,9]，它可以表示为:

示例 1：

  • 输入：head = [4,5,1,9], node = 5
  • 输出：[4,1,9]
  • 解释：给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

示例 2：

  • 输入：head = [4,5,1,9], node = 1
  • 输出：[4,5,9]
  • 解释：给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
     

提示：

  • 链表至少包含两个节点。
  • 链表中所有节点的值都是唯一的。
  • 给定的节点为非末尾节点并且一定是链表中的一个有效节点。
  • 不要从你的函数中返回任何结果。

解题思路：

  1. 无法直接获取被删除节点的上个节点
  2. 将被删除节点转移到下个节点
    即：如果要删除1节点 则需要先把9节点的值赋值给1节点，即4-5-9-9，然后删除最后一个节点 即 4-5-9

解题步骤：

  • 将被删除的节点的值改为下个节点的值
  • 删除下个节点

复杂度：

  • 时间复杂度O（1）
  • 空间复杂度O（1）
/*
 * @param {ListNode} node
 * @return {void} Do not return anything, modify node in-place instead.
 */
var deleteNode = function(node) {
    node.val = node.next.val;
    node.next = node.next.next;
    // 删除一个节点即 将本来要删除的节点的指针 指向下个节点的下个节点。
};

LeetCode #206 反转链表

反转一个单链表。

示例:

  • 输入: 1->2->3->4->5->NULL
  • 输出: 5->4->3->2->1->NULL

解题思路

  1. 假如：反转两个节点：将n+1的next指向n
  2. 假如：反转多个节点：双指针遍历链表，重复上述操作

解题步骤：

  1. 双指针一前一后遍历链表
  2. 遍历过程中不断反转双指针

复杂度：

  • 时间复杂度 O（n）
  • 空间复杂度 O（1）
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    let p1 = head;
    let p2 = null;
    while(p1){
        const temp = p1.next;
        p1.next = p2;
        p2 = p1;
        p1 = temp;
    }
    return p2;
};

LeetCode #83 删除排序链表中的重复元素

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。

示例 :

  • 输入: 1->1->2
  • 输出: 1->2
  • 输入: 1->1->2->3->3
  • 输出: 1->2->3

解题思路：

  1. 因为 链表是有序的，所以重复元素一定相邻
  2. 遍历链表，如果发现当前元素和下个元素值相同，就删除下个元素值

解题步骤：

  1. 遍历链表，如果发现当前元素和下个元素值相同，就删除下个元素值
  2. 遍历结束以后，返回原链表的头部

复杂度：

  1. 时间复杂度：O（n）
  2. 空间复杂度：O（1）
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function(head) {
    let p = head;
    while(p && p.next){
        if(p.val === p.next.val){
            p.next = p.next.next;
        }else{
            p = p.next;
        }
    }
    return head;
};

LeetCode # 141 环形链表

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false

示例一：

  • 输入：head = [3,2,0,-4], pos = 1
  • 输出：true
  • 解释：链表中有一个环，其尾部连接到第二个节点

示例二：

  • 输入：head = [1,2], pos = 0
  • 输出：true
  • 解释：链表中有一个环，其尾部连接到第一个节点。

示例三：

  • 输入：head = [1], pos = -1
  • 输出：false
  • 解释：链表中没有环。

提示：

  • 链表中节点的数目范围是 [0, 104]
  • -105 <= Node.val <= 105
  • pos 为 -1 或者链表中的一个 有效索引 。

解题思路:

  1. 两个人在圆形操场上的起点同时起跑，速度快的人一定会超过速度慢的人一圈。
  2. 用一快一慢两个指针遍历链表，如果指针能够相逢，那么链表就有圈

解题步骤:

  1. 用一快一慢两个指针遍历链表，如果指针能够相逢，就返回true
  2. 遍历结束后，还没有相逢就返回false

复杂度:

  1. 时间复杂度 O（n）
  2. 空间复杂度 O（1）
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function(head) {
    let p1 = head; // 慢指针
    let p2 = head; // 快指针
    while(p1 && p2 && p2.next){
        p1 = p1.next;
        p2 = p2.next.next;
        if(p1 === p2){ //两个指针相逢
            return true;
        }
    }
    return false;
};

前端与链表：JS中的原型链

原型链介绍

  • 原型链的本质是链表
  • 原型链上的节点是各种原型对象，比如Function.prototype、Object.prototype
  • 原型链通过_proto_属性连接各种原型对象

原型链长啥样？

  • obj -> Object.prototype -> null
  • func -> Function.prototype -> Object.prototype -> null
  • arr -> Array.prototype -> Object.prototype -> null

Coding Part

原型链知识点

  • 如果A沿着原型链能找到B.prototype，那么A instanceof B 为true
  • 如果在A对象上没有找到x属性，那么会沿着原型链找x属性

面试题一

简述instanceof的原理，并实现

  • 知识点： 如果A沿着原型链能找到B.prototype，那么A instanceof B 为true
  • 解法：遍历A的原型链，如果找到B.prototype，返回true，否则返回false
// 和遍历链表思路一样
const instanceOf = (A, B) => {
  let p = A;
  while(p){
    if(p === B.prototype){
      return true;
    }
    p = p.__proto__;
  }
  return false;
}

面试题二

var foo = {}, F = function(){};
Object.prototype.a = 'value a';
Function.prototype.b = 'value b';
console.log(foo.a);
console.log(foo.b);
console.log(F.a);
console.log(F.b);

分析：

  • 知识点：如果在A对象上没有找到x属性，那么会沿着原型链找x属性
  • 解法：明确foo和F变量的原型链，沿着原型链找a属性和b属性。
console.log(foo.a); // 'value a'
console.log(foo.b); // 'undefined'
console.log(F.a); // 'value a'
console.log(F.b); // 'value b'

前端与链表： 使用链表指针获取JSON的节点值

const json = {
  a: { b: {c: 1} },
  d: { e: 2 }
}

const path = ['d', 'e']; // 路径
// 和遍历链表异曲同工之妙
let p = json;
path.forEach(k =>{
  p = p[k];
})
// 路径：2

链表--总结

  • 链表里的元素存储不是连续的，之间通过next链接
  • JavaScript中没有链表，但可以用Object模拟链接
  • 链表常用操作：修改next，遍历链表
  • JS中的原型链也是一个链表。沿着proto属性
  • 使用链表指针可以获取JSON的节点值

阶段思考题：

  1. 编写一个 instanceOf 方法，可以判断一个变量是否是另一个变量的实例。
  2. 判断一个链表是否为回文链表。题目链接：https://leetcode-cn.com/problems/palindrome-linked-list/

声明：Xuhao's Blog|版权所有，违者必究|如未注明，均为原创|本网站采用BY-NC-SA协议进行授权

转载：转载请注明原文链接 - 数据结构（四）链表

Carpe Diem and Do what I like