[失业前端恶补算法]JavaScript leetcode刷题top100（三）

专栏声明：只求用最简单的，容易理解的方法通过，不求优化，不喜勿喷
今天更新五个 easy 难度题目：

相交链表

• 题面
  给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
  图示两个链表在节点 c1 开始相交：
  题目数据 保证 整个链式结构中不存在环。
  注意，函数返回结果后，链表必须 保持其原始结构 。

• 知识点：
  链表

• 思路
  你可以这样理解，如果我们先跑一次 A 链表，再跑一次 B 链表，和你先跑一次 B 链表 ，再跑一次 A 链表，遍历的节点数就一样了。那么如果 A 和 B 链表有相同的部分的话，只要我们遍历 A 和 B ，以及 B 和 A 各一次，那么遍历过程中出现指向同一个节点的情况就说明后续部分是一致的。所以我们按顺序遍历 A 和 B ，如果遍历到底部了，则换一个链表继续遍历，如果过程中出现了指向同一个节点的情况，则返回这个节点

• 代码

var getIntersectionNode = function(headA, headB) {if (headA === null || headB === null) {return null;}let pA = headA, pB = headB;while (pA !== pB) {pA = pA === null ? headB : pA.next;pB = pB === null ? headA : pB.next;}return pA;
};

多数元素

• 题面
  给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
  你可以假设数组是非空的，并且给定的数组总是存在多数元素。

• 知识点
  哈希表、分治法

• 思路
  我们先将数组的第一个数字作为基准，我们依次遍历数组，如果和基准一样，则计数+1，否则计数 -1，如果计数归 0 ，说明这个作为我们基准的数字目前出现频率不高，我们换用当前的数字作为基准继续操作，最后活下来的数字就是我们需要的数字。
  用更加形象的方式解释就是，现在有很多个军队打架，每次遇到不是自己阵营的人，那么一个队友就要和敌人一换一。现在从数组第一个位置的阵营开始检索，如果遇到了和当前阵营一样的就是友军，当前阵营的人数 + 1；否则就是敌军需要一个友军和敌军一换一，所以当前阵营人数 - 1 。如果阵营的人数归 0 ，那么这个阵容暂时就团灭了，我们从团灭他们的阵营开始新的遍历。最后活下来的阵营就是超过半数的阵营，因为他们一换一后至少多余一个人，所以遍历过程中肯定不会被团灭。

• 代码

var majorityElement = function (nums) {let count = 0;let win = -1;for (var i = 0; i < nums.length; i++) {if (count == 0) {win = nums[i];count++;}else if(win == nums[i]){count++;}else{count--;}}return win;
};

反转链表

• 题面
  给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
• 知识点
  链表
• 思路
  头插法形成链表，从前往后遍历链表，每次将当前的节点插入到头部，所以随着链表的遍历，最先插入的节点会来到最尾部，所以头部最先遍历的节点最后来到了末尾，而链表尾部最后遍历的节点就会来到链表的头部，从而完成了链表的反转
• 代码

var reverseList = function (head) {let prev = null;let curr = head;while (curr) {const next = curr.next;curr.next = prev;prev = curr;curr = next;}return prev;
};

翻转二叉树

• 题面
  给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
• 知识点
  二叉树、深度优先搜索
• 思路
  深度优先遍历整棵二叉树，对于每个节点，将二叉树的左右孩子对换，然后继续遍历二叉树的左子树和右子树
• 代码

var invertTree = function(root) {let dfs = function(node){if(!node){return ;}t = node.left;node.left = node.right;node.right = t;if(node.right){dfs(node.right)}if(node.left){dfs(node.left)}}dfs(root);return root;
};

回文链表

• 题面
  给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

• 知识点
  链表、回文、快慢指针

• 思路
  我们先找到链表的中间位置，使用一快一慢两个指针，快的一次走两步，慢的走一步，这样当快的指针到达的时候，慢的指针将会对准链表的中间位置。注意，我们每次都让两个指针都走一步，如果快指针到达底部了则停止程序，没有到达则让它再走一步。这样处理后，如果是奇数的链表，指针会停在中间，偶数的链表则停在第 （ n/2 +1 ）的位置。
  之后我们从慢指针的位置开始反转整个链表，代码逻辑在上面的题目里已经讲过了。反转完毕后，我们从头开始遍历原来的前半部分链表和反转的后半部分的链表，如果两者元素相同则是回文链表，否则不是。

• 代码

var isPalindrome = function(head) {let t = head;let b = head;let a = head;while(b){b = b.next;a = a.next;if(b){b = b.next;}}let re = null;while( a ){let t = a.next;a.next = re;re = a;a = t;}while(re){if(t.val != re.val){return false;}t = t.next;re = re.next;}return true;
};