模拟链表

  1. class Node {
  2.     constructor(value) {
  3.         this.value = value;
  4.         this.next = null;
  5.     }
  6. }
  8. class LinkedList {
  9.     constructor() {
  10.         this.length = 0;
  11.         this.head = null;
  12.     }
  14.     equalsFn(a, b) {
  15.         return a === b;
  16.     }
  17. }

功能

  1. push(element)：向链表尾部添加一个新元素。
  2. insert(element, position)：向链表的特定位置插入一个新元素。
  3. getElementAt(index)：返回链表中特定位置的元素。如果链表中不存在这样的元素，则返回undefined。
  4. remove(element)：从链表中移除一个元素。
  5. indexOf(element)：返回元素在链表中的索引。如果链表中没有该元素则返回-1。
  6. removeAt(position)：从链表的特定位置移除一个元素。
  7. isEmpty()：如果链表中不包含任何元素，返回true，如果链表长度大于0 则返回false。
  8. size()：返回链表包含的元素个数，与数组的length 属性类似。
  9. toString()：返回表示整个链表的字符串。由于列表项使用了Node 类，就需要重写继承自JavaScript 对象默认的toString 方法，让其只输出元素的值。

push

  1.     push(val) {
  2.         let newNode = new Node(val);
  3.         let curr;
  4.         if (!this.head) {   // 刚开始链表为空，就把这个设置为head
  5.             this.head = newNode;
  6.         } else {
  7.             curr = this.head;
  8.             while (curr.next) {    // 一直找到链表末尾
  9.                 curr = curr.next;
  10.             }
  11.             curr.next = newNode;
  12.         }
  13.         this.length++;
  14.     }

removeAt

链表 - 图1

  1.     removeAt(index) {
  2.         if (index < this.length && index >= 0) {
  3.             let curr = this.head;
  4.             if (index === 0) {
  5.                 this.head = curr.next;
  6.             } else {
  7.                 // 找到index前一个后停止，下一个就是要删除的结点
  8.                 for (let i = 1; i < index; i++) {
  9.                     curr = curr.next;
  10.                 }
  11.                 let beRemove = curr.next;
  12.                 // 改变要被删除结点的上一个结点的指向
  13.                 curr.next = beRemove.next;
  14.                 this.length--;
  15.                 return beRemove;
  16.             }
  17.         }
  18.     }

getElementAt

  1.     getElementAt(index) {
  2.         if (index < this.length && index >= 0) {
  3.             let curr = this.head;
  4.             if (index === 0) return curr;
  5.             else {
  6.                 for (let i = 1; i <= index; i++) {
  7.                     curr = curr.next;
  8.                 }
  9.                 return curr;
  10.             }
  11.         }
  12.     }

重写removeAt

  1.     removeAt(index) {
  2.         let curr = this.getElementAt(index - 1);
  3.         curr.next = curr.next.next;

insert

链表 - 图2

  1.     insert(index, value) {
  2.         let newNode = new Node(value);
  3.         if (index < this.length && index >= 0) {
  4.             let curr = this.head;
  5.             if (index === 0) {  // index 为0，改变头结点指向就行了
  6.                 this.head = newNode;
  7.                 this.head.next = curr;
  8.             } else {
  9.                 // 找到插入位置的前一个，
  10.                 for (let i = 1; i < index; i++) {
  11.                     curr = curr.next;
  12.                 }
  13.                 let nextNode = curr.next;
  14.                 curr.next = newNode;
  15.                 newNode.next = nextNode;
  16.             }
  17.             this.length++;
  18.         }
  19.     }

indexOf

  1.     indexOf(value) {
  2.         let curr = this.head;   // 存入head
  3.         if (this.equalsFn(curr.value, value)) {
  4.             return 0;
  5.         }
  6.         for (let i = 1; i < this.length; i++) {
  7.             curr = curr.next;
  8.             if (this.equalsFn(curr.value, value)) {
  9.                 return i;
  10.             }
  11.         }
  13.         return -1;
  14.     }

removeValue

  1.     removeValue(value) {
  2.         let curr = this.head;
  3.         let prev = null;
  4.         if (this.equalsFn(curr.value, value)) {
  5.             this.head = curr.next;
  6.             this.length--;
  7.         }
  8.         for (let i = 1; i < this.length; i++) {
  9.             prev = curr;
  10.             curr = curr.next;
  11.             if (this.equalsFn(curr.value, value)) {
  12.                 prev.next = curr.next;
  13.                 this.length--;
  14.             }
  15.         }
  16.         return undefined;
  17.     }

toString

  1.     toString() {
  2.         let objString = "";
  3.         let curr = this.head;
  4.         if (!curr) {
  5.             return objString;
  6.         } else {
  7.             objString = `${curr.value}`;
  8.             for (let i = 1; i < this.length; i++) {
  9.                 curr = curr.next;
  10.                 objString = `${objString}, ${curr.value}`;
  11.             }
  12.             return objString;
  13.         }
  14.     }

完整代码

  1. class Node {
  2.     constructor(value) {
  3.         this.value = value;
  4.         this.next = null;
  5.     }
  6. }
  8. class LinkedList {
  9.     constructor() {
  10.         this.length = 0;
  11.         this.head = null;
  12.     }
  14.     equalsFn(a, b) {
  15.         return a === b;
  16.     }
  18.     push(val) {
  19.         let newNode = new Node(val);
  20.         let curr;
  21.         if (!this.head) {   // 刚开始链表为空，就把这个设置为head
  22.             this.head = newNode;
  23.         } else {
  24.             curr = this.head;
  25.             while (curr.next) {    // 一直找到链表末尾
  26.                 curr = curr.next;
  27.             }
  28.             curr.next = newNode;
  29.         }
  30.         this.length++;
  31.     }
  33.     removeAt(index) {
  35.         let curr = this.getElementAt(index - 1);
  36.         curr.next = curr.next.next;
  37.     }
  39.     getElementAt(index) {
  40.         if (index < this.length && index >= 0) {
  41.             let curr = this.head;
  42.             if (index === 0) return curr;
  43.             else {
  44.                 for (let i = 1; i <= index; i++) {
  45.                     curr = curr.next;
  46.                 }
  47.                 return curr;
  48.             }
  49.         }
  50.     }
  52.     insert(index, value) {
  53.         let newNode = new Node(value);
  54.         if (index < this.length && index >= 0) {
  55.             let curr = this.head;
  56.             if (index === 0) {  // index 为0，改变头结点指向就行了
  57.                 this.head = newNode;
  58.                 this.head.next = curr;
  59.             } else {
  60.                 // 找到插入位置的前一个，
  61.                 for (let i = 1; i < index; i++) {
  62.                     curr = curr.next;
  63.                 }
  64.                 let nextNode = curr.next;
  65.                 curr.next = newNode;
  66.                 newNode.next = nextNode;
  67.             }
  68.             this.length++;
  69.         } else {
  70.             throw "索引值错误";
  71.         }
  72.     }
  74.     indexOf(value) {
  75.         let curr = this.head;   // 存入head
  76.         if (this.equalsFn(curr.value, value)) {
  77.             return 0;
  78.         }
  79.         for (let i = 1; i < this.length; i++) {
  80.             curr = curr.next;
  81.             if (this.equalsFn(curr.value, value)) {
  82.                 return i;
  83.             }
  84.         }
  86.         return -1;
  87.     }
  89.     removeValue(value) {
  90.         let curr = this.head;
  91.         let prev = null;
  92.         if (this.equalsFn(curr.value, value)) {
  93.             this.head = curr.next;
  94.             this.length--;
  95.         }
  96.         for (let i = 1; i < this.length; i++) {
  97.             prev = curr;
  98.             curr = curr.next;
  99.             if (this.equalsFn(curr.value, value)) {
  100.                 prev.next = curr.next;
  101.                 this.length--;
  102.             }
  103.         }
  104.         return undefined;
  105.     }
  107.     toString() {
  108.         let objString = "";
  109.         let curr = this.head;
  110.         if (!curr) {
  111.             return objString;
  112.         } else {
  113.             objString = `${curr.value}`;
  114.             for (let i = 1; i < this.length; i++) {
  115.                 curr = curr.next;
  116.                 objString = `${objString}, ${curr.value}`;
  117.             }
  118.             return objString;
  119.         }
  120.     }
  122.     getHead() {
  123.         return this.head;
  124.     }
  126.     isEmpty() {
  127.         return this.length === 0 ? true : false;
  128.     }
  130.     size() {
  131.         return this.length;
  132.     }
  133. }
  135. let linkedList = new LinkedList();
  136. linkedList.push("a");
  137. linkedList.push("b");
  138. linkedList.push("c");
  139. // linkedList.removeAt(1);
  140. linkedList.insert(1, "aa");
  141. console.log(linkedList.getElementAt(2));
  142. console.log(linkedList.indexOf("a"));
  143. console.log(linkedList.removeValue("c"));
  144. console.log(linkedList.size());
  145. console.log(linkedList.isEmpty());
  146. console.log(linkedList);
  147. console.log(linkedList.toString());

题目

lc237：删除链表中的结点

  1. var deleteNode = function(node) {
  2.     node.val = node.next.val;
  3.     node.next = node.next.next;
  4. };

206. 反转链表

  1. 双指正法
  2. 最开始p1指向head，p2指向前一个null
  3. 改变p1.next，主意首先保存temp = p1.next；
  4. 改变p2 = p1，p1 = temp，双指针向前移动，直到p1为null
  5. 返回p2，此时p2为新的head
    1. var reverseList = function(head) {
    2.  let p1 = head;
    3.  let p2 = null;
    4.  while(p1) {
    5.      const temp = p1.next;
    6.      p1.next = p2;
    7.      p2 = p1;
    8.      p1 = temp;
    9.  }
    10.  return p2;
    11. };

2. 两数相加

  1. var addTwoNumbers = function (l1, l2) {
  2.     const l3 = new ListNode(0);
  3.     let p1 = l1, p2 = l2;
  4.     let p3 = l3;
  5.     let carry = 0;  // 上一步的进位
  7.     while(p1 || p2) {
  8.         const val1 = p1 ? p1.val : 0;
  9.         const val2 = p2 ? p2.val : 0;
  10.         const x = val1 + val2 + carry;
  11.         carry = Math.floor(x / 10);
  12.         p3.next = new ListNode(x % 10);
  14.         if (p1) p1 = p1.next;
  15.         if (p2) p2 = p2.next;
  16.         p3 = p3.next;
  17.     }
  19.     if (carry) {
  20.         p3.next = new ListNode(carry)
  21.     }
  22.     return l3.next;
  23. };

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

  1. var deleteDuplicates = function(head) {
  2.     let p = head;
  4.     while(p && p.next) {
  5.         if (p.val === p.next.val) {
  6.             p.next = p.next.next;
  7.         } else {
  8.             p = p.next;
  9.         }
  10.     }
  11.     return head;
  12. };

141. 环形链表

快慢指针

  1. var hasCycle = function(head) {
  2.     let p1 = head;
  3.     let p2 = head;
  4.     while(p1 && p2 && p2.next) {
  5.         p1 = p1.next;
  6.         p2 = p2.next.next;
  7.         if (p1 === p2) {
  8.             return true
  9.         }
  10.     }
  11.     return false
  12. };

利用链表获取JSON的结点值

  1. const json = {
  2.     a: { b: { c: 1 } },
  3.     d: { e: 2 },
  4. };
  6. // 写出结点的路径
  7. const path = ["a", "b", "c"];
  9. let p = json;
  10. path.forEach(k => {
  11.     p = p[k];
  12. });
  14. console.log(p)