text: /**
   * 由于链表在空间的合理利用上和插入，删除时不需要移动等的有点，因此在很多场合下，它是线性表的首选存储结构。然而，它也存在着实现某些基本操作，如求线性表长度时不如顺序存储结构的缺点；另一方面，由于在链表中，结点之间的关系使用指针来表示，则数据元素在线性表中的“位序”的概念已淡化，而被数据元素在线性链表中的“位置”所代替。为此，从实际出发重新定义线性链表及其基本操作
   */
  
  class Node {
      constructor(data = null, next = null){
          this.data = data;
          this.next = next;
      }
  }
  
  export default class LinkedList {
      constructor(sqList = []){
          this.head = null;
          this.tail = null;
  
          if (sqList) {
              for (let i = 0, len = sqList.length; i < len; ++i)
                  this.push(sqList[i]);
          } 
      }
      
      /**
       * merge list, note: this operation will delete a and b nodes.
       * @param {LinkedList} a 
       * @param {LinkedList} b
       * @param {*} compare 
       */
      static mergeList (a, b, compare = compFn) {
          let ha = a.head;
          let hb = b.head;
          let pa = ha;
          let pb = hb;
          let c = new LinkedList();
          let q;
  
          while (pa && pb) {
              let data1 = pa.data;
              let data2 = pb.data;
  
              if (!compare(data1, data2)) {
                  // delete head node
                  q = a.shift();
                  // append the node to c linkedList
                  c.append(q);
                  pa = a.head;
              } else {
                  q = b.shift();
                  c.append(q);
                  pb = b.head;
              }
          }
          
          if (pa) {
              c.append(pa);
              c.tail = a.tail;
          }
          else {
              c.append(pb);
              c.tail = b.tail;
          }
          
          return c;
      }
  
      /**
       * remove the first element and return it
       */
      shift () {
          let head = this.head;
          this.head = this.head.next;
          head.next = null;
  
          if (this.head === null) this.tail = null;
          return head;
      }
  
      /**
       * remove the last element and return it
       */
      pop(){
          let current = this.head;
          let previous = this.head;
          let elem;
  
          while (current !== null) {
              if (this.tail === current) {
                  if (current === this.head) {
                      elem = this.tail.data;
                      this.head = null;
                      break;
                  }
  
                  this.tail = previous;
  
                  previous.next = current.next;
                  elem = current.data;
                  break;
              }
  
              previous = current;
              current = current.next;
          }
  
          if (this.head === null) this.tail = null;
  
          return elem ? elem : false;
      }
  
      /**
       * append node
       * @param {Node} node 
       */
      append (node) {
          if (this.head !== null) {
              this.tail.next = node;
              this.tail = this.tail.next;
          } else {
              this.head = node;
              this.tail = node;
          }
      }
  
      /**
       * add data
       * @param {*} data 
       */
      push (data) {
          if (this.head === null) {
              this.head = new Node(data);
              this.tail = this.head;
          } else {
              this.tail.next = new Node(data);
              this.tail = this.tail.next;
          }
  
          this.tail.data = data;
      }
  
      /**
       * remove data
       * @param {*} data 
       */
      remove (data) {
          let current = this.head;
          let previous = this.head;
          let elem;
  
          while (current !== null) {
              if (data === current.data) {
                  if (current === this.head) {
                      this.head = current.next;
                      elem = current.data;
                      break;
                  }
  
                  if (current === this.tail) this.tail = previous;
  
                  previous.next = current.next;
                  elem = current.data;
                  break;
              }
  
              previous = current;
              current = current.next;
          }
  
          if (this.head === null) this.tail = null;
  
          return elem ? elem : false;
      }
  
      /**
       * find the index of matched data 
       * @param {*} data 
       */
      indexOf(data){
          let current = this.head;
          let index = -1;
          while (current !== null) {
              ++index;
              if (current.data === data) {
                  return index;
              }
  
              current = current.next;
          }
  
          return index;
      }
  
      /**
       * add data to the front
       * @param {*} data 
       */
      unshift (data) {
          let temp = new Node(data);
          temp.next = this.head;
          this.head = temp;
      }
  
      /**
       * 
       * @param {*} target 
       * @param {*} data 
       */
      insertAfter (target, data) {
          let current = this.head;
          while (current !== null) {
              if (current.data === target) {
                  let temp = new Node(data);
                  temp.next = current.next;
  
                  if (current === this.tail) this.tail = temp;
  
                  current.next = temp;
                  return;
              }
  
              current = current.next;
          }
      }
  
      item (index) {
          let current = this.head;
  
          while (current !== null) {
              if (--index === 0) return current;
  
              current = current.next;
          }
  
          return null;
      }
  
      forEach (callback) {
          if (typeof callback !== 'function') return;
  
          for (let current = this.head, index = 0; current; current = current.next) {
              if (callback(current.data, index++)) break;
          }
      }
  
      *[Symbol.iterator](){
          for(let current = this.head; current; current = current.next){
              yield current.data;
          }
      }
  
      get size () {
          let current = this.head;
          let size = 0;
  
          while (current !== null) {
              ++size;
              current = current.next;
          }
  
          return size;
      }
  
      toString () {
          let str = '';
  
          this.forEach((node) => {
              str += node.data + (node.next ? ',' : '');
          });
  
          return str;
      }
  
      /**
       * insert element by order
       * @param {*} data 
       * @param {Function} cmp 
       */
      orderInsert (data, cmp) {
          cmp = typeof cmp === 'function' ? cmp : (a, b) => {
              if (a > b)
                  return 1;
              else if (a === b)
                  return 0;
              else
                  return -1;
          };
          let previous = this.head;
          let current = this.head;
  
          if (current === null) {
              this.head = this.tail = new Node(data);
              return;
          }
  
          let me = this;
          while (current) {
              let ret = cmp(data, current.data);
              // 如果插入元素大于当前元素，准备下次遍历
              if (ret > 0) {
                  previous = current;
                  current = current.next;
  
                  // 如果等于，直接插入到后面
              } else if (ret === 0) {
                  return insertBetween(data, previous, current);
  
                  // 如果小于则插入到前节点和当前节点中
                  // 因为已经是排序了，所以不需要多余判断了
              } else {
                  if (this.head === previous && previous === current)
                      return this.unshift(data);
                  else
                      return insertBetween(data, previous, current);
              }
          }
  
          // 插入到最后一个结点
          previous.next = new Node(data);
          this.tail = previous.next;
  
          function insertBetween(data, a, b) {
              if (a == b) {
                  if (a == me.head)
                      return me.unshift(data);
              } else {
                  let temp = new Node(data);
                  temp.next = b;
                  a.next = temp;
                  return true;
              }
          }
      }
  
      // 删除元素递增排列的链表中值大于min，且小于max的所有元素
      deleteBetween (min, max) {
          let p = this.head;
  
          // p是最后一个不大于min的元素
          while (p.next && p.next.data <= min) p = p.next;
  
          // 如果还有比min更大的元素
          let q;
          if (p.next) {
              q = p.next;
              // q是第一个不小于max的元素
              while (q && q.data < max) q = q.next;
              p.next = q;
          }
  
          let last = q || p;
          while (last.next) last = last.next;
          this.tail = last;
      }
  
      // 删除元素递增排列的链表的重复元素
      deleteEqual () {
          let p = this.head;
          let q = p.next;
  
          while (p.next) {
              // 当相邻两元素不相等时，p,q都向后移
              if (p.data !== q.data) {
                  p = p.next;
                  q = p.next;
              } else {
                  while (q.data === p.data) q = q.next;
  
                  // 删除
                  p.next = q;
                  p = q;
                  q = p.next;
              }
          }
      }
  
      reverse () {
          let p = this.head;
          let q = p.next;
          let s = q.next;
          this.tail = p;
          p.next = null;
  
          while (s.next) {
              q.next = p;
              p = q;
              q = s;
              s = s.next;
          }
  
          q.next = p;
          s.next = q;
          this.head = s;
      }
  }
  
  function compFn(a, b) {
      return a - b;
  }
  