题目
给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x 的节点之前。
你应当 保留 两个分区中每个节点的初始相对位置。（满足条件的元素的顺序不变）
我的解答
创建两条新的链表，分别是大于x和小于x的链表，遍历一遍head链表就可以填满两条新链表。
最后把两条链表收尾想接就成了满足条件的链表了。
注意这里也使用了虚拟头节点方便创建。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| public ListNode partition(ListNode head, int x) {
ListNode h1 = new ListNode() ,h2 = new ListNode();
ListNode p1 = h1,p2 = h2,p=head;
while (p != null){
if(p.val < x){
p1.next = p;
p1 = p1.next;
}else{
p2.next = p;
p2 = p2.next;
}
p=p.next;
}
p2.next = null;
p1.next = h2.next;
return h1.next;
}
|
官方参考
思路完全一致，代码都完全一致。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
public ListNode partition(ListNode head, int x) {
ListNode small = new ListNode(0);
ListNode smallHead = small;
ListNode large = new ListNode(0);
ListNode largeHead = large;
while (head != null) {
if (head.val < x) {
small.next = head;
small = small.next;
} else {
large.next = head;
large = large.next;
}
head = head.next;
}
large.next = null;
small.next = largeHead.next;
return smallHead.next;
}
}
|
链接：https://leetcode.cn/problems/partition-list/