刚开始刷LeetCode上链表相关的题目，在此记录下，本文主要包括：添加js链表代码模版-webstorm代码模版（这样刷题就不用每次都重新写了），头插法、尾插法、递归合并两个有序链表。

一、添加js链表代码模版

将下面的代码复制，然后打开webstorm设置，然后如下图中1 2 3 4，按顺序点击2中加号后，点击Live Templates，然后3中是自定的模版名字，复制代码模版到4中，然后点击应用后在webstorm里打出自定的模版名字就可以使用。

/**
* 链表节点
* @param {*} val
* @param {ListNode} next
*/
function ListNode(val, next = null) {
this.val = val;
this.next = next;
}
/**
* 将数组转为链表
* @param {array} array
* @return {ListNode}
*/
const getListFromArray = (array) => {
let dummy = new ListNode()
let pre = dummy;
array.forEach(x => pre = pre.next = new ListNode(x));
return dummy.next;
}
/**
* 打印链表
* @param {ListNode} list
*/
const logList = (list) => {
let str = 'list: ';
while (list) {
    str += list.val + '->';
    list = list.next;
}
str += 'null';
console.log(str);
}

二、头插法

使用头插法建立单链表，头插法是将一个新结点插入到链表的头节点之后，链表中元素顺序和读入数据的顺序相反，也可以用于链表逆序。
合并两个有序链表，本问题的实现中分为以下几种情况，l1和l2均为空，l1 l2至少一个不为空（分三种，全不为空，l1空，l2空）

// 初始化
l1 = [1, 2, 4];
l2 = [1, 3, 4];
l1 = getListFromArray(l1)
l2 = getListFromArray(l2)
logList(mergeTwoLists(l1,l2))

function mergeTwoLists(l1, l2) {
if (!l1 && !l2) { //均为空的情况
    return l1;
}
let head = new ListNode(null); // 头指针
while (l1 || l2) { //有一个不为空
    let s; // 临时指针
    //均不为空
    while (l1 && l2 && l1.val <= l2.val) { 
    // 头插法
    let tail = new ListNode(null); // 临时的新节点
    tail.val = l1.val;
    tail.next = head.next;
    head.next = tail;
    l1 = l1.next;
    }
    while (l1 && l2 && l1.val > l2.val) {
    let tail = new ListNode(null);
    tail.val = l2.val
    tail.next = head.next;
    head.next = tail;
    l2 = l2.next;
    }
    //l1存在l2为空，对l1剩下的进行头插法到head中
    if (l1 && !l2) {
    s = l1;
    l1 = l1.next;
    s.next = head.next
    head.next = s; 
    } else if (!l1 && l2) { //l1为空l2存在
    s = l2;
    l2 = l2.next;
    s.next = head.next
    head.next = s;
    }
}
return head;
}

三、尾插法

尾插法使用一个尾指针，始终指向表尾，建立的链表元素顺序和插入的数据顺序相同。主要代码如下：

function mergeTwoLists(l1, l2) {
if (!l1 && !l2) { //均为空的情况
    return l1;
}
let head = new ListNode(null); //新头指针
let t = head; //尾指针
while (l1 || l2) { //有一个不为空
    let s;//辅助指针
    //均不为空
    while (l1 && l2 && l1.val <= l2.val) {
    let tail = new ListNode(null); //新节点
    tail.val = l1.val; //将值赋给新节点
    t.next = tail //尾指针指向新节点，新节点为表尾了
    t = tail;  //将尾指针移到表尾
    l1 = l1.next;
    }
    while (l1 && l2 && l1.val > l2.val) {
    let tail = new ListNode(null);
    tail.val = l2.val
    t.next = tail
    t = tail;
    l2 = l2.next;
    }
    //l1存在l2为空
    if (l1 && !l2) {
    s = l1;
    l1 = l1.next;
    t.next = s;
    t = s;
    } else if (!l1 && l2) { //l1为空l2存在
    s = l2;
    l2 = l2.next;
    t.next = s;
    t = s;
    }
}
return head;
}

四、递归合并链表

var mergeTwoLists = function (l1, l2) {
    
if (!l1 || !l2) { // 先判断为空的情况，同时也是递归的边界
    return l2 || l1;
}
if (l1.val < l2.val) { //递归
    l1.next= mergeTwoLists(l1.next,l2);
    return l1;
}else{
    l2.next =  mergeTwoLists(l1,l2.next);
    return l2;
}
};