2020-05-28 5 kyu Linked Lists -

https://www.codewars.com/kata/55e1d2ba1a3229674d000037

My answer / AC

function Node(data) {
  this.data = data === undefined ? null : data;
  this.next = null;
}

function frontBackSplit(source, front, back) {
  if(!source) throw Error;
  if(source && !source.next) throw Error;
  
  var length=0;
  var pointer=source;
  var arr=[];
  while(true){
    arr.push(pointer.data);
    length++;
    if(pointer.next == null) break;
    pointer = pointer.next;
  }
  var mid = length%2 === 0 ? length/2 : Math.floor(length/2)+1;
  
  console.log(construct(front, arr, mid));

  
  console.log(source)
  
  pointer = source;
  var bpointer = back;
  var k=1;
  while(k<=mid){
    pointer = pointer.next;
    k++;
  }
  console.log(k)
  for(var j=k;j<=length; j++){
    if(j!==k){
      bpointer.next = pointer.next;
      pointer = pointer.next;
      bpointer = bpointer.next;
    }
    bpointer.data = pointer.data;
  }
  bpointer.next = null;
  
}

function construct(start, arr, num, acc=0){
  if(acc+1>num) return null;
  start.data = arr[acc];
  start.next = construct(new Node(), arr, num, acc+1);
  return start;
}

我边测试边用递归做这道题，突然通过了，一脸蒙蔽

Best answer

function Node(data) {
  this.data = data === undefined ? null : data;
  this.next = null;
}

Node.prototype.copy = function(source) {
    this.data = source.data
    this.next = source.next
};

function frontBackSplit(source, front, back) {
  if (!source || !source.next) throw "Invalid List"

  front.copy(source)
  
  for (slow = fast = front; fast;) {
    tail = slow
    slow = slow.next
    if (!fast.next) break
    fast = fast.next.next
  }
  
  back.copy(slow)  
  tail.next = null
}

• 这里用的是快慢指针的写法，效率更高，也更好懂。
• 值得学习的是这里的prototype的新定义，额能够直接将当前节点的东西赋值到Node对象里。

Recap

• 还挺开心的，第一次写递归能够AC（虽然是以这种糊里糊涂的方式）