链表是什么？

  • 多个元素组成的列表
  • 一般以链表的头节点表示该链表
  • 元素存储不连续，用 next 指针连在一起

链表 - 图1

数组 VS 链表

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

JS 中的链表

  • JS 中没有链表，使用 Object 来模拟链表 ```javascript 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;

// 遍历链表 // 1.声明一个指针，指向头节点 let p = a; while(p) { console.log(p.val); p = p.next; }

// 插入 const e = { val: ‘e’ } e.next = c.next; c.next = e;

// 删除 e c.next = e.next;

  1. <a name="jn1Vw"></a>
  2. ### LeetCode 题
  4. - 237.删除链表中的节点
  5.    - 思路
  6.       - 无法直接获取被删除节点的上一个节点
  7.       - 将被删除节点转移到下一个节点，或者说将下一个节点的值移到前一个节点
  8. - 206.反转链表
  9.    - 思路
  10.       - 先考虑两个节点的反转，将 n+1 的 next 指向 n
  11.       - 再考虑反转多个节点：双指针遍历链表，重复上述操作
  12. ```javascript
  13. // 1.创建两个指针，一前一后遍历链表
  14. // 2.不断反转双指针
  16. var reverseList = function(head) {
  17.   let p1 = head;
  18.   let p2 = null;
  19.   while(p1) {
  20.     let temp = p1.next;
  21.     p1.next = p2;
  22.     p2 = p1;
  23.     p1 = temp;
  24.   }
  25.   // p1 最后指向了 null
  26.   return p2;
  27. }
  • 2.两数相加