链表

Frank
  • 数据结构与算法
  • 链表
大约 6 分钟约 1851 字...

简介

注意

链表头就是一个链表,因为链表是一个串,你拿起来头,自然拿起来一串

多个元素组成的列表。

元素存储不连续,用 next 指针连在一起。

链表1

在数组中增删非首尾元素时往往需要移动元素,链表在增删非首尾元素,不需要移动元素,只需要更改 next 的指向即可。

js 中没有链表,需要用 Object 模拟:

const a = { val: 'a' }
const b = { val: 'b' }
const c = { val: 'c' }
const d = { val: 'd' }

// 创建
a.next = b
b.next = c
c.next = d

// 遍历
let p = a //声明一个指针指向a
while (p) {
  console.log(p.val)
  p = p.next
}
// 插入e
const e = { val: 'e' }
c.next = e
e.next = d
console.log(a)
// 删除e
c.next = d

LeetCode:237.删除链表中的节点

LeetCode:237.删除链表中的节点open in new window

  • 解题思路

无法直接获取被删除节点的上个节点

把要删除的下个结点的值赋给被删除节点,然后将被删除节点的下一节点删除

比如 1-2-3-4 要删除 3,先 1-2-4-4 然后删除最后一个 4,最后变成 1-2-4

  • 解题步骤

将被删节点的值改为下个节点的值。

删除下个节点。

/*
 * @lc app=leetcode.cn id=237 lang=javascript
 *
 * [237] 删除链表中的节点
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @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
}
// @lc code=end

LeetCode:206.反转链表

LeetCode:206.反转链表open in new window

  • 解题思路

反转两个节点:将 n+1 的 next 指向 n

反转多个节点:双指针遍历链表,重复上述操作。

  • 解题步骤

双指针一前一后遍历链表。

反转双指针。

解法一
/*
 * @lc app=leetcode.cn id=206 lang=javascript
 *
 * [206] 反转链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  let [p1, p2] = [head, null]
  while (p1) {
    let tmp = p1.next
    p1.next = p2
    p2 = p1
    p1 = tmp
  }
  return p2
}
// @lc code=end
解法二
/*
 * @lc app=leetcode.cn id=206 lang=javascript
 *
 * [206] 反转链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function (head) {
  let [p1, p2] = [head, null]
  while (p1) {
    ;[p1.next, p2, p1] = [p2, p1, p1.next]
  }
  return p2
}
// @lc code=end

LeetCode:2. 两数相加

LeetCode:2. 两数相加open in new window

  • 解题思路

小学数学题,模拟相加操作

需要遍历链表

  • 解题步骤

新建一个空链表

遍历被相加的两个链表,模拟相加操作,将个位数追加到新链表上,将十位数留到下一位去相加

/*
 * @lc app=leetcode.cn id=2 lang=javascript
 *
 * [2] 两数相加
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
  let l3 = new ListNode()
  let [p1, p2, p3, carry] = [l1, l2, l3, 0]
  while (p1 || p2) {
    let v1 = p1 ? p1.val : 0
    let v2 = p2 ? p2.val : 0
    let val = v1 + v2 + carry
    carry = Math.floor(val / 10)
    p3.next = new ListNode(val % 10)
    if (p1) p1 = p1.next
    if (p2) p2 = p2.next
    p3 = p3.next
  }
  if (carry) p3.next = new ListNode(carry)
  return l3.next
}
// @lc code=end

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

LeetCode:83. 删除排序链表中的重复元素open in new window

  • 解题思路

    因为链表是有序的,所以重复元素一定相邻

    遍历链表,如果发现当前元素和下个元素值相同,就删除下个元素值

  • 解题步骤

遍历链表,如果发现当前元素和下个元素值相同,就删除下个元素值

遍历结束后,直接返回原链表的头部(head)

/*
 * @lc app=leetcode.cn id=83 lang=javascript
 *
 * [83] 删除排序链表中的重复元素
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var deleteDuplicates = function (head) {
  let p1 = head
  while (p1 && p1.next) {
    if (p1.val === p1.next.val) {
      p1.next = p1.next.next
    } else {
      p1 = p1.next
    }
  }
  return head
}
// @lc code=end

LeetCode:141. 环形链表

LeetCode:141. 环形链表open in new window

  • 解题思路

两个人在圆形操场上的起点同时起跑,速度快的人一定会超过速度慢的人一圈

用一快一慢两个指针遍历链表,如果指针能够相逢,那么链表就有圈。

环形链表

  • 解题步骤

用一快一慢两个指针遍历链表,如果指针能够相逢,就返回 true。

遍历结束后,还没有相逢就返回 false。

/*
 * @lc app=leetcode.cn id=141 lang=javascript
 *
 * [141] 环形链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */

/**
 * @param {ListNode} head
 * @return {boolean}
 */
var hasCycle = function (head) {
  let [slow, fast] = [head, head]
  while (slow && fast && fast.next) {
    slow = slow.next
    fast = fast.next.next
    if (slow === fast) return true
  }
  return false
}
// @lc code=end

LeetCode: 234. 回文链表

LeetCode: 234. 回文链表open in new window

  • 解题思路

回文就是反转以后和以前一样的就是回文结构,例如 1->2->3->2->1,我们将它反转之后还是与原链表一样,我们就称这种链表结构为回文结构

  • 解题步骤

快慢指针,起初都指向表头,快指针一次走两步,慢指针一次走一步,遍历结束时:

要么,slow 正好指向中间两个结点的后一个。

要么,slow 正好指向中间结点。

用 prev 保存 slow 的前一个结点,通过prev.next = null断成两个链表。

将后半段链表翻转(参考 leetcode.206),和前半段从头比对。

回文链表

/*
 * @lc app=leetcode.cn id=234 lang=javascript
 *
 * [234] 回文链表
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {boolean}
 */
var isPalindrome = function (head) {
  // 链表只有一个节点的情况
  if (head.next == null) {
    return true
  }
  let [fast, slow, prev] = [head, head, null]
  while (fast && fast.next) {
    prev = slow
    slow = slow.next
    fast = fast.next.next
  }
  // 断成两个链表
  prev.next = null
  // 翻转后半段
  let head2 = null
  while (slow) {
    // 解构赋值,不用使用临时变量
    // ;[slow.next, head2, slow] = [head2, slow, slow.next]
    let temp = slow.next
    slow.next = head2
    head2 = slow
    slow = temp
  }
  // 前后两段进行比较
  while (head && head2) {
    if (head.val !== head2.val) {
      return false
    }
    head = head.next
    head2 = head2.next
  }
  return true
}
// @lc code=end

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

原型链的本质是链表

原型链上的节点是各种原型对象, 比如 Function.prototypeObject.prototype……

原型链通过__proto__属性连接各种原型对象。

面试题:instanceof 的原理,并用代码实现。

知识点:如果 A 沿着原型链能找到B.prototype,那么A instanceof B为 true。

解法:遍历 A 的原型链,如果找到B.prototype,返回 true,否则返回 false

面试题:看输出

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

知识点:如果在 A 对象上没有找到 ⅹ 属性,那么会沿着原型链找 ⅹ 属性。

解法:明确 foo 和 F 变量的原型链,沿着原型链找 a 属性和 b 属性。

链表面试题2

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

const json = {
  a: { b: { c: 1 } },
  d: { e: 2 },
}
const path = ['d', 'e']

let p = json

path.forEach((k) => {
  p = p[k]
})
上次编辑于:
评论
  • 按正序
  • 按倒序
  • 按热度
Powered by Waline v2.14.1