一面主要是过往自己认为最优秀的项目讲解，问的比较细；
二面两个算法题比较简单，一个是LintCode 96原题，另一个是给定一组区间表示登陆登出时间，求同时段最大在线人数。
亚麻面试非常喜欢考原题，想在短时间内突击面试的话，可以多刷几遍高频题，或者上九章的高频题班，都可以大大节约准备算法面试的时间。
下面主要看下这道题在LintCode上的解法。
题目：链表划分 Partition list
描述：
给定一个单链表和数值x，划分链表使得所有小于x的节点排在大于等于x的节点之前。
你应该保留两部分内链表节点原有的相对顺序。
样例
样例 1:
输入: list = null, x = 0
输出: null
样例解释: 空链表本身满足要求
样例 2:
输入: list = 1->4->3->2->5->2->null, x = 3
输出: 1->2->2->4->3->5->null
样例解释: 要保持原有的相对顺序。
题解
双指针方法，用两个指针将两个部分分别串起来。最后在将两个部分拼接起来。
left指针用来串起来所有小于x的结点，
right指针用来串起来所有大于等于x的结点。
得到两个链表，一个是小于x的，一个是大于等于x的，做一个拼接即可。
这里可以在线评测并查看其他语言的解法
-
public
class Solution {
-
public ListNode partition(ListNode head, int x) {
-
if (head ==
null) {
-
return
null;
-
}
-
-
ListNode leftDummy =
new ListNode(
0);
-
ListNode rightDummy =
new ListNode(
0);
-
ListNode left = leftDummy, right = rightDummy;
-
-
while (head !=
null) {
-
if (head.val < x) {
-
left.next = head;
-
left = head;
-
}
else {
-
right.next = head;
-
right = head;
-
}
-
head = head.next;
-
}
-
-
right.next =
null;
-
left.next = rightDummy.next;
-
return leftDummy.next;
-
}
-
}
转载：https://blog.csdn.net/JiuZhang_ninechapter/article/details/104430074
查看评论