摘要
【面试必刷101】系列blog目的在于总结面试必刷101中有意思、可能在面试中会被考到的习题。总结通用性的解题方法，针对特殊的习题总结思路。既是写给自己复习使用，也希望与大家交流。
【面试必刷101】递归/回溯算法总结I（十分钟理解回溯算法）
【面试必刷101】递归/回溯算法总结II（十分钟刷爆回溯算法题）
1 链表基础知识
单链表
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
双链表
public class ListNode {
int val;
ListNode next = null;
ListNode pre = null;
ListNode(int val) {
this.val = val;
}
}
链表这类题感觉出的比较少，注意以下几个题型就可以了。
2 面试必刷习题
2.1 k个一组反转链表
普通的反转链表：
很简单的一张图，就是将当前节点指向前一个节点，然后将当前节点变成下一个节点来进行遍历。
import java.util.*;
public class Solution {
public class Solution {
public ListNode ReverseList(ListNode cur) {
ListNode pre = null;
ListNode next = null;
while (cur != null) {
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
然后来看链表中每k个节点一组翻转。
首先可以用递归来实现：每k个一组其实可以先做后面的再做前面的，大问题由很多小问题组成。
然后小问题可以用简单的链表翻转来做。具体看代码，还是很值得学习的。
import java.util.*;
public class Solution {
public ListNode reverseKGroup (ListNode head, int k) {
if (head == null || head.next == null) return head;
ListNode tail = head;
for (int i = 0; i < k; i++) {
if (tail == null) {
return head;
}
tail = tail.next;
}
// 翻转前k个元素
ListNode newHead = reverse(head, tail);
// head已经是最后一个元素了。这个递归很有灵性。
head.next = reverseKGroup(tail, k);
return newHead;
}
// 反转[head, tail)
public ListNode reverse (ListNode cur, ListNode tail) {
ListNode pre = null;
ListNode next = null;
while (cur != tail) {
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
2.2 合并k个链表
题目链接：BM5 合并k个已排序的链表
为啥这道题值得一做呢？主要考察点有三个：
- 合并策略是啥？ 基于归并排序思路的两两合并；优先队列。
- 怎么合并两个有序链表？ 建立一个头结点，谁小就插入谁。
import java.util.*;
public class Solution {
public ListNode mergeKLists(ArrayList<ListNode> lists) {
return mergeList(lists, 0, lists.size() - 1);
}
public ListNode mergeList(ArrayList<ListNode> list, int l, int r) {
if (l== r) {
return list.get(l);
}
if (l > r) {
return null;
}
int mid = l + ((r - l) >> 1);
ListNode left = mergeList(list, l, mid);
ListNode right = mergeList(list, mid + 1, r);
return merge2Lists(left, right);
}
// 合并两个链表
public ListNode merge2Lists(ListNode list1, ListNode list2) {
ListNode head = new ListNode(0);
ListNode cur = head;
while (list1 != null && list2 != null) {
if (list1.val > list2.val) {
cur.next = list2;
list2 = list2.next;
} else {
cur.next = list1;
list1 = list1.next;
}
cur = cur.next;
}
if (list1 != null) cur.next = list1;
if (list2 != null) cur.next = list2;
return head.next;
}
}
2.3 链表相加
题目链接：链表相加（二）
乍一眼看起来好难呀？该从哪里开始相加呢？不清楚。为啥不清楚，因为从next Node找不到pre Node，这就是单链表的特点。但是，如果翻转之后就很好做了。
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/
public class Solution {
/**
*
* @param head1 ListNode类
* @param head2 ListNode类
* @return ListNode类
*/
public ListNode addInList (ListNode head1, ListNode head2) {
ListNode h1 = reverse(head1);
ListNode h2 = reverse(head2);
int tag = 0;
int val = 0;
ListNode cur = null, pre = null;
while (h1 != null || h2 != null) {
if (h1 != null) {
val += h1.val;
h1 = h1.next;
}
if (h2 != null) {
val += h2.val;
h2 = h2.next;
}
val += tag;
if (val >= 10) {
tag = 1;
val = val % 10;
} else {
tag = 0;
}
cur = new ListNode(val);
val = 0;
cur.next = pre;
pre = cur;
}
if (tag == 1) {
cur = new ListNode(1);
cur.next = pre;
}
return cur;
}
public ListNode reverse (ListNode cur) {
ListNode pre = null;
ListNode next = null;
while (cur != null) {
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
2.4 单链表的排序
题目链接：BM12单链表的排序。
