K神面试精选 88 题
K神是hello-algo的作者，官网地址为：hello算法；题目地址为：Krahets 笔面试精选 88 题;
409. 最长回文串（20250220更新）
题目给出一个字符串，让我们使用字符串s的所有字符能够构成多长的回文字串。
回文串分为奇数和偶数回文串，奇数的话除了中间的一个字符个数为1，其他的字符出现的次数都是偶数。
所以可以使用哈希表来维护字符串s的每个字符的出现次数，然后在遍历，如果出现的次数是奇数个，就向下去偶数， 加到变量res上，然后将odd修改成1，以此类推。
class Solution {
public int longestPalindrome(String s) {
// 统计字符出现次数
Map<Character, Integer> cnt = new HashMap<>();
for(int i = 0;i<s.length();i++){
cnt.merge(s.charAt(i), 1, Integer::sum);
}
int res = 0, odd = 0;
// 遍历判断
for(Map.Entry<Character, Integer> entry: cnt.entrySet()){
int value = entry.getValue();
if(value % 2 == 1){
value -= 1;
odd = 1;
}
res += value;
}
return res + odd;
}
}20. 有效的括号（20240616更新）
就是利用栈的特性，匹配到成对的括号就出栈。
定义一个哈希表，用来对应括号的另一半。
当时 ({[的时候就压栈，不然的话就出栈，判断出栈的元素能否与字节匹配。
237. 删除链表中的节点（20240616更新）
常规的想要删除链表中的一个节点的思路是，获取到删除节点的钱节点pre， 删除节点为cur， 执行操作 pre.next = cur.next;cur.next = null;
但是现在获取不到前节点，可以将后一个节点的值复制到删除节点上，然后用上面方法，把cur.next删掉
Java
class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}Python
Code...206. 反转链表（20240612更新）
给你单链表的头节点head，返回反转后的链表。
执行如下步骤：
- 暂存头节点后面节点 ListNode tmp = head.next
- 定义ListNode pre = null, 把head.next 接到pre后面
- 移动pre 指向head.next
- 移动cur 指向tmp
Java
class Solution {
public ListNode reverseList(ListNode head) {
ListNode cur = head, pre = null;
while(cur != null){
ListNode tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
}Python
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
cur, pre = head, None
while cur != None:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
return preJS
var reverseList = function(head) {
let cur = head, pre = null;
while(cur != null){
let tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
}
return pre;
};21. 合并两个有序链表（20240611更新）
合并两个有序的链表，因为是有序链表，所以使用双指针指向两个链表的头部，比较两个节点的大小，将小的放到虚拟头结点的后面。
这里有几个注意点：
- 使用虚拟头结点，最后返回的时候返回虚拟头结点的next节点
- 判断链表不为空，直接判断
list != null, 不是判断list.next != null, 因为list.next = null, 表示next为空，list不为空 - 将没有比较完的节点接到虚拟链表后面，不用一个一个循环接，直接
dummy.next = list
Java
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode dummy = new ListNode(-1), p=dummy;
ListNode p1 = list1, p2 = list2;
while(p1 != null && p2 != null){ // p1.next?
if(p1.val <= p2.val){
p.next = p1;
p1 = p1.next;
}else{
p.next = p2;
p2 = p2.next;
}
p = p.next;
}
if(p1 != null){ // 要循环将后面节点放到p后面吗？
p.next = p1;
}
if(p2 != null){
p.next = p2;
}
return dummy.next; // 返回虚拟头结点的next
}
}Python
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
p = dummy
p1, p2 = list1, list2
while p1 != None and p2 != None:
if p1.val <= p2.val:
p.next = p1
p1 = p1.next
else:
p.next = p2
p2 = p2.next
p = p.next
if p1 != None:
p.next = p1
if p2 != None:
p.next = p2
return dummy.nextJS
var mergeTwoLists = function(list1, list2) {
let dummy = new ListNode(-1), p = dummy;
let p1 = list1, p2 = list2;
while(p1 != null && p2 != null){
if(p1.val <= p2.val){
p.next = p1;
p1 = p1.next;
}else{
p.next = p2;
p2 = p2.next;
}
p = p.next;
}
if(p1!=null){
p.next = p1;
}
if(p2!=null){
p.next = p2;
}
return dummy.next;
};