【LintCode 题解】亚马逊中国二面算法题 ：链表划分
一面主要是过往自己认为最优秀的项目讲解，问的比较细；
二面两个算法题比较简单，一个是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;
}
}
作者：九章算法
相关文章
Serafina
2021-03-06
Hea
2020-10-30
Irisa
2020-12-23
Angie
2023-05-12
Jacinda
2023-05-13
Rhea
2023-05-31
Kathy
2023-07-07
Trixie
2023-07-20
Maleah
2023-07-20
Hester
2023-07-20
Ianthe
2023-07-20
Valora
2023-07-20
Grizelda
2023-07-20
Jayne
2023-07-20
Fern
2023-07-20
Gita
2023-07-20
Radinka
2023-07-20