链表

设计链表

题目编号：707
设计链表

/**
 * 链表节点构造函数
 */
function Node(val) {
  this.val = val;
  this.next = null;
};

/**
 * Initialize your data structure here.
 */
var MyLinkedList = function() {
  this.head = null;
};

/**
 * 获取指定索引的node节点
 */
MyLinkedList.prototype.getNode = function (index) {
  var curIndex = 0;
  var curNode = this.head;
  if (curNode) {
    while(curNode.next !== null && curIndex < index) {
      curNode = curNode.next;
      curIndex++;
    }
    return curIndex === index ? curNode : -1;
  } else {
    return -1;
  }
}

/**
 * Get the value of the index-th node in the linked list. If the index is invalid, return -1. 
 * @param {number} index
 * @return {number}
 */
MyLinkedList.prototype.get = function(index) {
  var node = this.getNode(index);
  return node !== -1 ? node.val : -1;
};

/**
 * Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtHead = function(val) {
  var node = new Node(val);
  if (this.head) node.next = this.head;
  this.head = node;
};

/**
 * Append a node of value val to the last element of the linked list. 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtTail = function(val) {
  var curNode = this.head;
  var node = new Node(val);
  if (curNode.next === null) {
    curNode.next = node;
  } else {
    while(curNode.next !== null) {
      curNode = curNode.next;
      if (curNode.next === null) {
        curNode.next = node;
        break;
      }
    }
  }
};

/**
 * Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. 
 * @param {number} index 
 * @param {number} val
 * @return {void}
 */
MyLinkedList.prototype.addAtIndex = function(index, val) {
  var node = new Node(val);
  var prev = index - 1;
  if (prev < 0) this.addAtHead(val);
  var prevNode = this.getNode(prev);
  if (prevNode) {
    node.next = prevNode.next;
    prevNode.next = node;
  }
};

/**
 * Delete the index-th node in the linked list, if the index is valid. 
 * @param {number} index
 * @return {void}
 */
MyLinkedList.prototype.deleteAtIndex = function(index) {
  var delNode = this.getNode(index);
  if (delNode !== -1) {
    if (index === 0) {
      this.head = this.head.next;
    } else {
      var prev = index - 1;
      var prevNode = this.getNode(prev);
      prevNode.next = delNode.next;
    }
  }
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * var obj = new MyLinkedList()
 * var param_1 = obj.get(index)
 * obj.addAtHead(val)
 * obj.addAtTail(val)
 * obj.addAtIndex(index,val)
 * obj.deleteAtIndex(index)
 */

总结

1. 方法逐步累加，确保前面的方法考虑情况周全，后续使用不会出问题；
2. 本题的解题顺序最好是先写生成链表结构的代码，编写测试代码，例如 travel()，检验链表结构是否生成正确，随后才补充操作链表的相关方法，其它的题目也应该进行合理的模块拆分。

反转链表

题目编号：206
反转链表

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
  if (!head || !head.next) return head;

  let reverseHead = head;

  while (head.next) {
    let preHeadNode = reverseHead;
    let rdNode = head.next.next;

    reverseHead = head.next;
    reverseHead.next = preHeadNode;
    head.next = rdNode;
  }

  return reverseHead;
};