数据结构--链表

[lznbuild]

链表

像火车，车厢和车厢之间连接，可以随时替换车厢。链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大

链表的模拟实现

  // 辅助类：节点
  class Node  {
    constructor(element){
      this.element = element; // 当前节点的值
      this.next = null // 当前节点指向下一个节点的指针 
    }
  }

  class likedList {
    constructor(){
      // 链表头
      this.head = null;
      // 链表长度
      this.length = 0;
    }



    // 链表尾添加元素
    append (element) {
      var node = new Node(element);

      if (this.head == null) {
        // 只会在向链表添加第一次的时候执行
        this.head = node
        this.length++
      } else {
        var current = this.head;
        while (current.next) {
          current = current.next
        }

        //while执行完毕后，current.next 为null,current是链表的最后一项
        current.next = node;
        this.length++;
      }
    }


    //链表某一个位置添加元素
    insert (position, element) {
      //越界
      if (position > -1 && position < this.length) {
        var node = new Node(element);

        if (position == 0) {
          var current = this.head;
          this.head = node;
          this.head.next = current
          this.length++
        } else {
          var index = 0;
          var current = this.head;
          var previous = null;
          while (index < position) {
            previous = current;
            current = current.next;
            index++;
          }
          previous.next = node;
          node.next = current
        }

        this.length++
      }
    }

    // 删除某一个位置的元素
    removeAt (position) {
      if (position > -1 && position < this.length) {
        if (position == 0) {
          this.head = this.head.next;
        } else {
          var current = this.head;
          var previous = null;
          var index = 0;
          while (index < position) {
            previous = current;
            current = current.next;
            index++;
          }

          // 出循环的时候，index == position
          previous.next = current.next
        }


        this.length--;
        return current //返回删除项
      }
      return null
    }

    //删除某一项
    remove (element) {
      return this.removeAt(this.indexOf(element))
    }

    // 查找
    indexOf (element) {
      var current = this.head;
      var index = 0;
      while (current) {
        if (current.element == element) {
          return index
        }
        index++;
        current = current.next
      }

      return -1
    }


    isEmpty () {
      return this.length == 0
    }

    size () {
      return this.length
    }


    getHead() {
      return this.head
    }
  }

链表的反转

const reverseList = function(head) {
    // 初始化前驱结点为 null
    let pre = null;
    // 初始化目标结点为头结点
    let cur = head;
    // 只要目标结点不为 null，遍历就得继续
    while (cur !== null) {
        // 记录一下 next 结点
        let next = cur.next;
        // 反转指针
        cur.next = pre;
        // pre 往前走一步
        pre = cur;
        // cur往前走一步
        cur = next;
    }
    // 反转结束后，pre 就会变成新链表的头结点
    return pre
};

链表的删除

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

示例 1:
输入: 1->1->2
输出: 1->2

示例 2:

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

const deleteDuplicates = function(head) {
    // 设定 cur 指针，初始位置为链表第一个结点
    let cur = head;
    // 遍历链表
    while(cur != null && cur.next != null) {
        // 若当前结点和它后面一个结点值相等（重复）
        if(cur.val === cur.next.val) {
            // 删除靠后的那个结点（去重）
            cur.next = cur.next.next;
        } else {
            // 若不重复，继续遍历
            cur = cur.next;
        }
    }
    return head;
};

真题描述：给定一个排序链表，删除所有含有重复数字的结点，只保留原始链表中 没有重复出现的数字。

示例 1:
输入: 1->2->3->3->4->4->5
输出: 1->2->5

示例 2:
输入: 1->1->1->2->3
输出: 2->3

const deleteDuplicates = function(head) {
    // 极端情况：0个或1个结点，则不会重复，直接返回
    if(!head || !head.next) {
        return head
    }
    // dummy 登场
    let dummy = new ListNode() 
    // dummy 永远指向头结点
    dummy.next = head   
    // cur 从 dummy 开始遍历
    let cur = dummy 
    // 当 cur 的后面有至少两个结点时
    while(cur.next && cur.next.next) {
        // 对 cur 后面的两个结点进行比较
        if(cur.next.val === cur.next.next.val) {
            // 若值重复，则记下这个值
            let val = cur.next.val
            // 反复地排查后面的元素是否存在多次重复该值的情况
            while(cur.next && cur.next.val===val) {
                // 若有，则删除
                cur.next = cur.next.next 
            }
        } else {
            // 若不重复，则正常遍历
            cur = cur.next
        }
    }
    // 返回链表的起始结点
    return dummy.next;
};

集合

es6中的set，不再赘述

字典

js中的对象，不再赘述