| Category | Difficulty | Likes | Dislikes |
|---|
| algorithms | Medium (55.90%) | 158 | - |
Tags
linked-list | two-pointers
Companies
Unknown
给定一个链表和一个特定值* x*，对链表进行分隔，使得所有小于 *x* 的节点都在大于或等于 *x* 的节点之前。
你应当保留两个分区中每个节点的初始相对位置。
示例:
1
2
| 输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5
|
Discussion | Solution
建立两个空链表smaller_list和bigger_list；
依次取出原链表结点，和target_val比较，小于target_val的加入smaller_list末尾；否则加入bigger_list末尾；
原链表所有节点取完后，如果bigger_list不为空，则加入到smaller_list结尾；ß
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| pub fn partition(head: Option<Box<ListNode>>, x: i32) -> Option<Box<ListNode>> {
if head.is_none() {
return head
}
let mut dummy_head1 = Some(Box::new(ListNode::new(0)));
let mut dummy_head2 = Some(Box::new(ListNode::new(0)));
let mut ptr1 = &mut dummy_head1;
let mut ptr2 = &mut dummy_head2;
let mut head = head;
while let Some(mut node) = head {
head = node.next.take();
if node.val < x {
ptr1.as_mut().unwrap().next = Some(node);
ptr1 = &mut ptr1.as_mut().unwrap().next;
} else {
ptr2.as_mut().unwrap().next = Some(node);
ptr2 = &mut ptr2.as_mut().unwrap().next;
}
}
if let Some(mut node) = dummy_head2.as_mut().unwrap().next.take() {
ptr1.as_mut().unwrap().next = Some(node);
}
dummy_head1.unwrap().next
}
|