1.链表的概念：

用一组任意存储的单元来存储线性表的数据元素。一个对象存储着本身的值和下一个元素的地址。

需要遍历才能查询到元素，查询慢。
插入元素只需断开连接重新赋值，插入快。

2.链表的结构：

3.链表常用的操作

单指针解法
双指针解法
哑节点解法
递归解法

4.链表的题目

题目一：从尾到头打印链表

输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

分析

要了解链表的数据结构：
val属性存储当前的值，next属性存储下一个节点的引用。
要遍历链表就是不断找到当前节点的next节点，当next节点是null时，说明是最后一个节点，停止遍历。
因为是从尾到头的顺序，使用一个队列来存储打印结果，每次从队列头部插入。

代码

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/
function printListFromTailToHead(head)
{
    const array = [];
    while(head){
        array.unshift(head.val);
        head = head.next;
    }
    return array;
}

注：unshift() 方法将新项添加到数组的开头，并返回新的长度。unshift和push是从两个不同的方向向数组中添加元素。
注释：unshift() 方法会改变数组的长度。
提示：如需在数组末尾添加新项，请使用 push() 方法。

题目2：反转链表

    function reverseLinkNode(){
        // 创建一个之前的节点
                var pre = null
                // 创建当前节点
                var cur = head
                // 若当前节点存在则进入循环
                while(cur){
                    next = cur.next
                    cur.next = pre
                    pre = cur
                    cur = next
                }
                // 当pre是空的时候说明循环已经结束链表已经到头
                return pre
            }

题目3：复制一个复杂链表

方法1：回溯算法+哈希表

本题要求我们对一个特殊的链表进行深拷贝。如果是普通链表，我们可以直接按照遍历的顺序创建链表节点。而本题中因为随机指针的存在，当我们拷贝节点时，「当前节点的随机指针指向的节点」可能还没创建，因此我们需要变换思路。一个可行方案是，我们利用回溯的方式，让每个节点的拷贝操作相互独立。对于当前节点，我们首先要进行拷贝，然后我们进行「当前节点的后继节点」和「当前节点的随机指针指向的节点」拷贝，拷贝完成后将创建的新节点的指针返回，即可完成当前节点的两指针的赋值。

具体地，我们用哈希表记录每一个节点对应新节点的创建情况。遍历该链表的过程中，我们检查「当前节点的后继节点」和「当前节点的随机指针指向的节点」的创建情况。如果这两个节点中的任何一个节点的新节点没有被创建，我们都立刻递归地进行创建。当我们拷贝完成，回溯到当前层时，我们即可完成当前节点的指针赋值。注意一个节点可能被多个其他节点指向，因此我们可能递归地多次尝试拷贝某个节点，为了防止重复拷贝，我们需要首先检查当前节点是否被拷贝过，如果已经拷贝过，我们可以直接从哈希表中取出拷贝后的节点的指针并返回即可。

在实际代码中，我们需要特别判断给定节点为空节点的情况。

方法二：迭代+节点拆分

题目4：题目：倒数第k个节点

/* 题目：倒数第k个节点 
思路：输入一个链表，输出该链表中倒数第k个结点。
简单思路： 循环到链表末尾找到 length 在找到length-k节点 需要循环两次。
优化：
设定两个节点，间距相差k个节点，当前面的节点到达终点，取后面的节点。
前面的节点到达k后，后面的节点才出发。
注意： 需要考虑head为null，k为0，k大于链表长度的情况。*/
function findKfromTail(head, k) {
  if (!head || !k) {
    return null
  }
  let front = head
  let back = head
  let count = 1
  while (front.next) {
    count++
    front = front.next
    if (count > k) {
      back = back.next
    }
  }
  return (k <= count) && back
}

题目5：输入两个链表，找出他们的第一个公共节点

/* 题目：输入两个链表，找出他们的第一个公共节点 */
/* 思路：
         1.先找到两个链表的长度：length1、length2;
         2.让长一点的链表先走length2-length1步，让长链表和短链表起点相同;
         3.两个链表一起前进，比较获得第一个相等的节点.
 */
// 创建获取该链表长度的函数
function getLength(head) {
  // 初始化长度和当前节点
  let current = head;
  let length = 0
  // 当链表没循环到底的时候就自增长度
  while (current) {
    current = current.next
    length++
  }
  return length
}
// 创建一个函数用来获取两个链表中相同的节点
function getSameNode(phead1, phead2) {
  // 判断是否为空,为空直接return
  if (!phead1 || !phead2) {
    return null
  } else {
    // 长链表先行
    let length1 = getLength(phead1)
    let length2 = getLength(phead2)
    // 若1的长度>2
    // 声明较长链表,较短链表和长度差
    let long, short, interval
    if (length1 > length2) {
      long = phead1
      short = phead2
      interval = length1 - length2
    } else {
      long = phead2
      short = phead1
      interval = length2 - length1
    }
    // 长链表先行
    while (interval--) {
      long = long.next
    }
    // 寻找相同节点
    while (long) {
      if (long == short) {
        return long
      }
      long = long.next
      short = short.next
    }
    return null
  }
}

题目6：合并两个排序的链表（从小到大）

/* 题目:输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。 */
/* 思路:1.链表头部节点比较，取较小节点。
        2.小节点的next等于小节点的next和大节点的较小值。
        3.如此递归。
        4.返回小节点。
        5.考虑代码的鲁棒性，也是递归的终止条件，两个head为null的情况，取对方节点返回 
*/
function Merge(pHead1, pHead2) {
  if (!pHead1) {
    return pHead2;
  }
  if (!pHead2) {
    return pHead1;
  }
  let head;
  if (pHead1.val < pHead2.val) {
    head = pHead1;
    head.next = Merge(pHead1.next, pHead2);
  } else {
    head = pHead2;
    head.next = Merge(pHead1, pHead2.next);
  }
  return head;
}
var mergeTwoLists = function(l1, l2) {
if(!l1){
  return l2
}else if(!l2){
  return l1
}else if(l1.val<l2.val){
  l1.next = mergeTwoLists(l1.next,l2)
  return l1
}else{
  l2.next = mergeTwoLists(l1,l2.next)
  return l2
}
};

题目7：删除倒数第n个节点

思路：

双指针方法（设置双指针中间隔n个，先让第一个指针指向头部，第二个指针向后走n个节点；然后两个节点同时向后走，当第二个指针指向尾部的时候，第一个指针指的就是要删除的节点）

var removeNthFromEnd = function(head, n) {
let fast = head,slow =head
while(fast && n>0){
[fast,n] = [fast.next,n-1]
}
if(!fast){
  return head.next
}
while(fast.next){
  [fast,slow] = [fast.next,slow.next]
}
slow.next = slow.next.next
return head
};

优化：

双指针方法虽然能解决问题，但是当我们遇到要删除的节点是头部节点的时候就没有办法跟原来一样返回头部节点了。所以需要借助哑节点来解决问题——哑节点是在处理与链表相关的操作时，设置在链表头之前的指向链表头的节点，用于简化与链表头相关的操作。

题目8：给定值删除对应的节点

解法：单指针、双指针、哑节点、递归

代码示例：

//单指针
function deleteNode(head, val) {
  if (head.val == val) return head.next;
  let cur = head;
  while (cur.next) {
    if (cur.next.val == val) {
      cur.next = cur.next.next;
      return head;
    }
    cur = cur.next;
  }
  return head;
}
//dummy 单指针
function deleteNode( head,  val) {
    let dummy = new ListNode(-1,head); 
    let pre = dummy;
    while (cur.next) {
      if (cur.next.val == val) {
        cur.next = cur.next.next;
        return dummy.next;
      }
      cur = cur.next;
    }
    return dummy.next;
}
//双指针
function deleteNode( head,  val) {
    if(head.val == val) return head.next;
    let pre = head, cur = head.next;
    while (cur) {
      if (cur.val == val) {
        pre.next = cur.next;
        return head;
      }
      pre = cur;
      cur = cur.next;
    }
    return head;
}
//dummy 双指针
function deleteNode(head, val) {
    let dummy = new ListNode(-1, head);
    let pre = dummy,cur = head; 
    while (cur) {
      if (cur.val == val) {
        pre.next = cur.next;
        return dummy.next;
      }
      pre = cur;
      cur = cur.next;
    }
    return dummy.next;
};
//递归
var deleteNode = function(head, val) {
    if(head.val == val) return head.next
    head.next = deleteNode(head.next,val);
    return head
};