链表javascript实现
链表（Linked list）是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺
序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度
分别是O(logn)和O(1)。
javascript实现可以通过下面的方法：
function ListNode(val) {
this.val = val;
this.next = null;
}
下面我们看看链表题目的基本类型:
删除
删除的题目有19, 83, 203, 237, 82
删除其实就是找到要删除元素的前一个元素pre;
pre.next = pre.next.next;
不过还有一种是假删除，找前一个元素比较麻烦，我们可以直接把要删除元素的下一个元素的值赋给当前删除，然后删除下一个元素；
cur.val = cur.next.val;
cur.next = cur.next.next;
看一个典型例题19. Remove Nth Node From End of List:
Given a linked list, remove the nth node from the end of list and return its head.
For example,
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
这个题目我们可以通过设置两个变量，fast变量先走n步，然后fast和slow变量同时走，直到fast为null; 此时slow就是到达了倒数第n个元素，执行删除即可；代码如下：
var removeNthFromEnd = function(head, n) {
var left, before, right = head;
left = before = {next: head};
while (n--) right = right.next;
while (right) {
right = right.next;
left = left.next;
}
left.next = left.next.next;
return before.next;
};
查找
查找题目有：160, 141, 142
我们来看看141. Linked List Cycle，判断是否🈶️环，我们可以通过设置两个指针fast和slow，slow一次走一步，fast一次走两部，如果🈶️环，fast必定在环内追上slow；于是：
var hasCycle = function(head) {
var slow = head;
var fast = head;
while(fast && fast.next) {
fast = fast.next.next;
slow = slow.next;
if(fast === slow) {
return true;
}
}
return false;
};
翻转
翻转题目有234，206，24，92，61
234. Palindrome Linked List其实是一个判断是否是回文的题目，但是我们可以利用翻转来判断；
首先利用两个变量来找到中间点，然后分为两个链表，把后面的链表翻转过来，并同时遍历两个链表比较：
var isPalindrome = function(head) {
function reverse(curr) {
var prev = null;
var next;
while(curr) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
var fast = head;
var slow = head;
while(fast && fast.next) {
fast = fast.next.next;
slow = slow.next;
}
if(fast) slow = slow.next;
slow = reverse(slow);
while(slow && head.val === slow.val) {
head = head.next;
slow = slow.next;
}
return slow === null;
};
合并
合并的题目有：21，328，86，148，2，92，143
86. Partition List这个题目是让我们把指定元素后面的都小于它的元素放到指定元素前面去；
我们可以设置两个表头，遍历链表，把小于指定元素的链接到第一个表，反之，链接到第二个表，最后把第二个链表链接到第一个链表后面；
var partition = function(head, x) {
var hd1 = new ListNode(0);
var hd2 = new ListNode(0);
var p1 = hd1;
var p2 = hd2;
while(head) {
if(head.val < x) {
p1.next = head;
p1 = p1.next;
} else {
p2.next = head;
p2 = p2.next;
}
head = head.next;
}
p2.next = null;
p1.next = hd2.next;
return hd1.next;
};
总结
其实链表的操作就是那几种：删除／查找／翻转／合并, 只要掌握链表的基本操作并配合标记或者特定题目的一些特性，基本都可以解决；