前端学数据结构与算法（四）：理解递归及拿力扣链表题目练手

function a() {
  b();
  console.log('a')
}
function b() {
  c();
  console.log('b')
}
function c() {
  console.log('c');
}

a(); // c b a

function recursion(params) {
  1. 递归终止条件  (避免无限递归)
  2. 当前函数层逻辑处理  (递归函数的主要处理逻辑)
  3. 进入下一层函数  (再次执行递归函数)
  4. 处理当前层函数其他逻辑  (可能有这一步，也可能没有)
}

function reverseStr(s) {
  if (s === "") { // 终止条件
    return "";
  }
  const lastC = s[s.length - 1]; // 字符串的最后一位
  const otherC = s.slice(0, -1); // 除去最后一位的其他字符串
  return lastC + reverseStr(otherC); // 进入递归下一层
}

反转一个单链表
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

var reverseList = function (head) {
  if (head === null || head.next === null) {
    return head
  }
  const node = reverseList(head.next) // 最后一个节点
  head.next.next = head // 让3指向2、让2指向1。
  head.next = null // 让2指向空、让1指向空。
  return node
};

给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
输入: 1->1->2
输出: 1->2

输入: 1->1->2->3->3
输出: 1->2->3

var deleteDuplicates = function (head) {
  if (head === null || head.next === null) {
    return head
  }
  const ret = deleteDuplicates(head.next) 
  // 递归到底去，因为递归的终结条件，ret就是最后一个节点
  // 而此时head就是倒数第二个节点
  
  if (ret.val === head.val) {
    head.next = ret.next // 倒数第二个节点指向它的下下个节点
  }
  return head
};

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

var mergeTwoLists = function (l1, l2) {
  if (l1 == null) { // l1到了头，说明l2接下来都比l1最大值还大
    return l2
  }
  if (l2 == null) { // 同理
    return l1
  }
  if (l1.val > l2.val) {
    l2.next = mergeTwoLists(l1, l2.next) // 则l2换下一个更大节点来比较
    return l2 // 当前小节点指向拼接好的结果后，返回
  } else {
    l1.next = mergeTwoLists(l1.next, l2) // 同理换更大的节点来比较
    return l1 // 同理
  }
};

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

 1->2->3->4, 返回 2->1->4->3.

var swapPairs = function (head) {
  if (head === null || head.next === null) { 
  	//判断head.next是为了防止链表节点个数是奇数
    
    return head
  }
  const firstNode = head // 链表的第一个节点
  const secondNode = head.next // 链表的第二个节点
  
  firstNode.next = swapPairs(secondNode.next) 
  // 第一个节点指向第二个节点之后已经交换好的链表
  
  secondNode.next = firstNode // 第二个节点指向第一个节点
  
  return secondNode // 返回第二个节点作为新的头节点
};

给定一个带有头结点 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
1->2->3->4->5
返回3->4->5

var middleNode = function (head) {
  let slow = head // 慢指针
  let fast = head // 快指针
  while (fast !== null && fast.next !== null) {
    fast = fast.next.next // 走两步
    slow = slow.next // 走一步
  }
  return slow // 走完后慢指针指向中间节点
};

给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
如果 pos 是 -1，则在该链表中没有环。

输入：3->2->0->-4，pos=1。 
输出：true。
尾部链接到下标1的位置，为有环。

输入：3->2->0->-4，pos=-1。
输入：false。
尾部没有链接，没环。

var hasCycle = function (head) {
  let slow = head
  let fast = head
  while(fast !== null && fast.next !== null) {
    slow = slow.next
    fast = fast.next.next
    if (slow === fast) { // 相遇了
      return true
    }
  }
  return false
};

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.

说明：给定的 n 保证有效。
进阶尝试：你能尝试使用一趟扫描实现吗？

var removeNthFromEnd = function (head, n) {
  const dummy = new ListNode() // 设置一个虚拟节点，统一边界处理
  dummy.next = head
  let slow = dummy // 因为要找的是待删除之前节点的缘故
  let fast = dummy.next // 让快指针事先就领先一步
  while (fast !== null) {
    if (n > 0) { // 先把领先的走完
      n--
      fast = fast.next
    } else { // 然后一起走
      fast = fast.next
      slow = slow.next // 走完后慢指针正好在待删除节点之前
    }
  }
  const delNode = slow.next
  slow.next = delNode.next // 移除待删除节点
  delNode.next = null
  return dummy.next // 返回头节点
};

力扣 109. 有序链表转换二叉搜索树
给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。