1.链表中倒数第 k 个结点
问题描述：
输入一个链表，输出该链表中倒数第 k 个结点。
解题思路 1：
因为要求链表倒数第 k 个节点，也就是求正数第 length - k 个节点。整体过程如下：
- 链表又是个单链表，并且没有保存长度信息。所以需要循环一次计算 length。
- 第二次循环找到第 length - k 个节点。
时间复杂度是 O(N)，需要 2 次循环。
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function FindKthToTail(head, k) {
// write code here
let length = 0;
let node = head;
while (node) {
length++;
node = node.next;
}
if (k > length) {
return null;
}
let offset = length - k;
node = head;
for (let i = 0; i < offset; i++) {
node = node.next;
}
return node;
}
解题思路 2：
准备两个指针：left（慢）和 right（快）。整体过程如下：
- right 先向右移动 k 位，此时 index(right) - index(left) = k
- left 和 right 一起向右移动，直到 right 抵达边界
- 由于 index(right) - index(left) = k，所以 index(left) = index(right) - k = length - k。也就是 left 指针移动到了倒数第 k 个位置
时间复杂度是 O(N)，但仅需要遍历一次。空间复杂度是 O（1）
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function FindKthToTail(head, k) {
let right = head;
for (let i = 0; i < k; ++i) {
if (right === null) {
// 链表长度小于k
return null;
}
right = right.next;
}
let left = head;
while (right) {
left = left.next;
right = right.next;
}
return left;
}
2.反转链表
问题描述：
输入一个链表，反转链表后，输出新链表的表头。
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function ReverseList(pHead) {
// write code here
let prev = null; // 上一个节点
var curr;
while (pHead) {
curr = pHead; // 当前节点
pHead = pHead.next;
curr.next = prev;
prev = curr;
}
return prev;
}
3.合并两个排序的链表
问题描述：
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
解题思路：
设置一个“哨兵节点”叫 pHead，整体流程如下：
如果 pHead1 和 pHead2，均没遍历完：
- 如果 pHead1.val <= pHead2.val，那么当前 node 的 next 指向 pHead1。并且移动 pHead1 指针。
- 否则，当前 node 的 next 指向 pHead2，移动 pHead2 指针。
- 移动 node 指针
- 继续循环
否则，结束循环：
- 如果 pHead1 未遍历完，node 的 next 指向 pHead1
- 如果 pHead2 未遍历玩，node 的 next 指向 pHead2
时间复杂度是 O(N)，空间复杂度是 O(1)。代码如下：
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function Merge(pHead1, pHead2) {
// write code here
if (!pHead1) {
// 如果pHead1链表不存在，就返回pHead2
return pHead2;
}
if (!pHead2) {
// 如果pHead2链表不存在，就返回pHead1
return pHead1;
}
let pHead = new ListNode(-1); // 新建一个‘哨兵节点’
let node = pHead; // 头节点的指针
while (pHead1 && pHead2) {
// pHead1 和 pHead2 都存在时
if (pHead1.val <= pHead2.val) {
node.next = pHead1;
pHead1 = pHead1.next;
} else {
node.next = pHead2;
pHead2 = pHead2.next;
}
node = node.next;
}
if (pHead1) {
// pHead1 链表长度大于 pHead2
node.next = pHead1;
}
if (pHead2) {
// pHead2 链表长度大于 pHead1
node.next = pHead2;
}
return pHead.next; // pHead是-1，所以是pHead.next
}
4.树的子结构
问题描述：
输入两棵二叉树 A，B，判断 B 是不是 A 的子结构。（ps：我们约定空树不是任意一个树的子结构）
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function HasSubtree(pRoot1, pRoot2) {
// 当pRoot2的根节点与pRoot1的根节点不同时就需要对pRoot1的左右子树进行遍历
// write code here
if (pRoot1 == null || pRoot2 == null) {
// pRoot1 pRoot2 有一个为null，结构就为false
return false;
}
return (
judgeSubtree(pRoot1, pRoot2) || // pRoot2是不是pRoot1的子结构
HasSubtree(pRoot1.left, pRoot2) || // pRoot1的左子树中有没有pRoot2
HasSubtree(pRoot1.right, pRoot2) // pRoot1的右子树中有没有pRoot2
);
}
function judgeSubtree(root1, root2) {
// 对root2进行遍历判断root2 是不是root1 的子结构
if (!root2) {
return true;
}
if (!root1) {
return false;
}
if (root1.val !== root2.val) {
return judgeSubtree(root1.left, root2) || judgeSubtree(root1.right, root2);
}
return (
judgeSubtree(root1.left, root2.left) &&
judgeSubtree(root1.right, root2.right)
);
}