每日算法（第十四期）

儿童节了也要好好学习鸭。

先来回顾一下上期的问题及答案：

「反转链表」（Reverse Linked List）。

题目描述： 反转一个单链表。

以下是对应的JavaScript实现：

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

解题思路：

• 使用迭代的方法反转链表。

• 初始化两个指针 prev 和 curr，分别指向前一个节点和当前节点。

• 在迭代过程中，用一个临时变量 nextTemp 保存当前节点的下一个节点。

• 将当前节点的指针指向前一个节点，然后更新 prev 和 curr 的位置。

• 最终返回反转后的链表的头节点。

时间复杂度分析：

• 迭代过程中，需要遍历整个链表一次，时间复杂度为 O(n)，其中 n 是链表的长度。

空间复杂度分析：

• 只使用了常量级别的额外空间，所以空间复杂度为 O(1)。

例如：

function ListNode(val, next) {this.val = val;this.next = next;
}const head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);const reversedList = reverseList(head);
console.log(reversedList); // { val: 5, next: { val: 4, next: { val: 3, next: { val: 2, next: { val: 1, next: null } } } } }

在上述例子中，给定一个链表 1->2->3->4->5，通过调用 reverseList 函数将链表进行反转。最终得到的反转后链表为 5->4->3->2->1。

2023年6月2日

「有效的括号」（Valid Parentheses）。

题目描述： 给定一个只包含字符 '(', ')', '{', '}', '[' 和 ']' 的字符串 s，判断字符串是否有效。

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。

2. 左括号必须以正确的顺序闭合。

注意空字符串可被认为是有效字符串。

提示如下：

• 使用栈来匹配括号。

• 遍历字符串，如果当前字符是左括号（'(', '[', '{'），则将其入栈。

• 如果当前字符是右括号（')', ']', '}'），则从栈顶取出一个字符，如果它与当前字符匹配，则继续遍历；否则返回 false。

• 最后，检查栈是否为空，如果为空则表示所有括号都匹配成功，返回 true；否则返回 false。

要求的结果：

console.log(isValid("()")); // true
console.log(isValid("()[]{}")); // true
console.log(isValid("(]")); // false
console.log(isValid("([)]")); // false
console.log(isValid("{[]}")); // true

在上述例子中，给定字符串分别为 "()"、"()[]{}"、"(]"、"([)]" 和 "{[]}"。通过调用 isValid 函数判断字符串是否有效。有效的字符串返回 true，无效的字符串返回 false。

上面问题的答案会在第二天的公众号推文中公布，大家可以关注公众号：程序员每日三问，第一时间获得推送内容。

学习不打烊，充电加油只为遇到更好的自己,每天早上9点纯手工发布面试题（死磕自己，愉悦大家） 希望大家在这浮夸的程序员圈里保持冷静，每天坚持花20分钟来学习与思考，在千变万化，类库层出不穷的今天，不要等到找工作时才狂刷题，提倡每日学习。