| Category | Difficulty | Likes | Dislikes |
|---|
| algorithms | Medium (54.54%) | 158 | - |
Tags
linked-list
Companies
Unknown
给定一个单链表 L：L0→L1→…→L**n-1→Ln ，
将其重新排列后变为： L0→L**n→L1→L**n-1→L2→L**n-2→…
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1:
1
| 给定链表 1->2->3->4, 重新排列为 1->4->2->3.
|
示例 2:
1
| 给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.
|
Discussion | Solution
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
| impl Solution {
/// ## 解法
/// 1. 将原链表从中间截断，
/// 2. 前半部分不变，后半部分倒序，
/// 3. 后将前后两个子链表合并；
pub fn reorder_list(head: &mut Option<Box<ListNode>>) {
if head.is_none() {
return
}
let mut len = 0;
{
let mut ptr = head.as_ref();
while let Some(node) = ptr {
len += 1;
ptr = node.next.as_ref();
}
}
if len < 2 {
return
}
let mut next = head.as_mut().unwrap().next.take();
let mut dummy_list1 = Some(Box::new(ListNode::new(0)));
let mut dummy_list2 = Some(Box::new(ListNode::new(0)));
{
let mut i = 0;
let cut_len = len / 2;
let mut tail_ptr1 = &mut dummy_list1;
while let Some(mut current_node) = next.take() {
i += 1;
next = current_node.next.take();
if i > cut_len {
current_node.next = dummy_list2.as_mut().unwrap().next.take();
dummy_list2.as_mut().unwrap().next = Some(current_node);
} else {
tail_ptr1.as_mut().unwrap().next = Some(current_node);
tail_ptr1 = &mut tail_ptr1.as_mut().unwrap().next;
}
}
}
{
let mut list1_tail_ptr = &mut dummy_list1;
let mut list2_next = dummy_list2.as_mut().unwrap().next.take();
while let Some(mut node) = list2_next {
list2_next = node.next.take();
node.next = list1_tail_ptr.as_mut().unwrap().next.take();
list1_tail_ptr.as_mut().unwrap().next = Some(node);
list1_tail_ptr = &mut list1_tail_ptr.as_mut().unwrap().next;
list1_tail_ptr = &mut list1_tail_ptr.as_mut().unwrap().next;
}
}
head.as_mut().unwrap().next = dummy_list1.as_mut().unwrap().next.take();
}
}
|