LinkedList flatten

flatten.js

// 极其弱的版本，对于[1, [], 2]这样的奇怪情况（嵌套的是空链）会跪，回头修回头修

var ListNode = function(value, next){
  // 虽然是简单结构，但是为了Hidden Type优化做成个class
  this.value = value;
  this.next = next;
};

var LinkedList = function(){
  this.head = this.tail = new ListNode(null, null);
};
LinkedList.prototype = {
  constructor: LinkedList,
  insert: function(value){
    /*
     * head -> ... -> tail -> null
     *      ^
     *    value
     */
    var node = new ListNode(value, this.head.next);
    if (node.next === null){
      this.tail = node;
    }
    this.head.next = node;

    return this;
  },
  append: function(value){
    if (this.head === this.tail) return this.insert(value);
    /*
     * head -> ... -> tail -> null
     *                     ^
     *                   value
     */
    var node = new ListNode(value, null);
    this.tail.next = node;
    this.tail = node;

    return this;
  },
  concat: function(that){
    /*
     * head -> ... -> tail -> null
     *                     ^
     *       that.head -> ... -> that.tail -> null
     */
    if (that.head === that.tail) return this;
    this.tail.next = that.head.next;
    this.tail = that.tail;

    return this;
  },
  debug: function(){
    var arr = [];
    var node = this.head;
    while (node){
      var text = node.value;
      if (node === this.head){
        text += '(head)';
      }
      if (node === this.tail){
        text += '(tail)';
      }
      arr.push(text);

      node = node.next;
    }
    console.log(arr.join(' -> '));
  },
  toArray: function(){
    var arr = [];
    var node = this.head.next;
    while (node){
      arr.push(node.value);
      node = node.next;
    }
    return arr;
  },
  toString: function(){
    //return '[Object LinkedList]'
    return '[ ' + this.toArray().join(', ') + ' ]';
  },
  flatten: function(){
    var node = this.head.next;
    while (node){
      var that = node.value;
      if (that instanceof LinkedList){
        that.flatten();
        that.tail.next = node.next;

        node.value = that.head.next.value;
        node.next = that.head.next.next;
      }

      node = node.next;
    }

    return this;
  }
};



var list = new LinkedList();
list.append(1)
    .append(2)
    .append(3);


var list2 = new LinkedList();
list2.append(5);
var list22 = new LinkedList();
list22.append(10);
list2.append(list22)
     .append(20);

var list3 = new LinkedList();
list3.append(100)
     .append(500);

list.append(list2).concat(list3);

console.log(list.toString());

console.log(list.flatten().toString());

/**
[ 1, 2, 3, [ 5, [ 10 ], 20 ], 100, 500 ]
[ 1, 2, 3, 5, 10, 20, 100, 500 ]
**/