反转链表

反转链表的递归解法，可以从链表的反向遍历理解：

• 通过递归的方式，一触到底，直接到达链尾
• 递归函数之后，为回溯即链表的从链尾的反向遍历
• 递归base：head触底时指向链尾，弹栈回溯时head为上一层的head，此时指向倒数第二个结点，所以

• 每一层的递归都保持引用反转后的新链表头，通过return的方式一直抛向最上层，直到最后作为链表结果返回

function reverseList(head){
    if(head==null||head.next ==null){
        return head;
    }
    let newhead = reverseList(head.next);
    head.next.next = head;
    head.next = null;// 断开原链接 不然要环
    return newhead;
}

同理进阶一下，反转链表的前n个结点

let tail_next = null; // 设置一个全局变量，保存反转区域的链表尾的下一个对接结点
function reverseN(head, n) {
  if (n === 1) {
    tail_next = head.next;
    return head;
  }
  // 链表新头结点
  let newhead = reverseN(head.next, n - 1);
  head.next.next = head;
  head.next = tail_next; // 对比反转整个链表时 此处为null,反转区间时应该继续接入到链表里去
  return newhead;
}

再进阶一下，反转链表的指定区间（m,n）
在反转前n个基础上改进，m指向的结点作为反转前n个结点的表头起始
m以前的区域head.next即指向反转前n个结点后的新表头

function reverseBetween(head, m, n) {
    let tail_next = null;// 反转区域的链表尾的下一个对接结点
    if (m == 1) {
        return reverseN(head, n);
    }
    // 前进到反转的起点触发 base case
    head.next = reverseBetween(head.next, m - 1, n - 1);// n在前n个里使用的计数
    return head;
    function reverseN(head, n) {
        if (n === 1) {
            tail_next = head.next;
            return head;
        }
        // 链表新头结点
        let last = reverseN(head.next, n - 1);
        head.next.next = head;
        head.next = tail_next; // 对比反转整个链表时 此处为null,反转区间时应该继续接入到链表里去
        return last;
    }
}

合并两个有序链表

迭代的思路：
两个指针同时遍历两链表，哪个结点小就将新链表的next赋给谁

递归：抽出当前两个节点中（head1 和 head2 中）较小的那个，然后把剩下的一股脑丢给递归

var mergeTwoLists = function(l1, l2) {
    if(l1==null) return l2;
    if(l2==null) return l1;
    if(l1.val<l2.val){
          // mergeTwoLists(l1.next,l2) 划分
          // return l1, l1.next 即是回溯过程做的事
        l1.next = mergeTwoLists(l1.next,l2);
        return l1;
    }else{
        l2.next  = mergeTwoLists(l1,l2.next);
        return l2;
    }
};

回文链表

通过递归的方式一触到底访问到链尾元素，同时通过全局变量的方式保留做链头元素
回溯的过程就是判断的过程

function isPalindrome(head) {
    let left = head;
    return traverse(head);

    function traverse(node) {
        if (node==null) return true;
        let prevIsSame = traverse(node.next);
        // 逆序输出code
        let currIsSame = left.val === node.val;
        left = left.next;// left通过这种方式向右，node通过弹栈的方式向左
        return prevIsSame && currIsSame;
    }
}

参考

递归实现链表操作