算法学习1:重新排序链表

算法学习:重新排序链表

欢迎交换友链: laker.me–进击的程序媛
Github:https://github.com/younglaker
V信: lakerHQ (请注明‘来自博客’)

题目

给定一个单链表,将链表按头节点、尾节点、第二个节点、 倒数第二个节点…的规律重建。要求:原地操作,不改变节点的值。

思路

暴力法:先找头节点,再找尾节点,然后顺次第二个节点,倒数第二个节点,由于是单链表,不停的从表头遍历到表尾,时间复杂度O(n^2)

看下有没有其他便捷方法。

假设给一组数字1,2,3,4,5,6,重新排序后是1,6,2,5,3,4,会发现一个规律,1, 2, 3是顺序的,6, 5, 4是倒序插入的。

所以可这样考虑:
先把链表一分为二,把后半部分数据倒序插入前半部分。
头插法制作倒序链表,时间复杂度 O(n),将左右两链表合并,时间复杂度 O(n)。总时间复杂度为O(n)。

伪代码

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
void Revert (Link L1) {
new Link L2; //用于存放倒序的后半部链表
int half_len = L1.lenght() / 2; //记录链表的一半
int *p = L1->head; //p 指向 L1 头节点
int *q = L2->head; //q 指向 L2 头指针
int *s, *t;
for (int i = 0; i < half_len; i++) {
s = s->next; // 找到链表中部
}
q = s->next; //把后半段链表赋值给 L2
s->next = null; // 此时 s 为 L1尾指针
t = q->next;
// 这里我直接在表内操作,看起来有点乱,新建个 L3来存放会看得舒服点
while ( t->next != null ) { //倒置 L2
q->next = t->next;
t->next = q;
L2->head->next = t;
t = q->next;
q = L2->head->next;
}
while ( p != s ) { // p 没有走到表尾时插入L2节点
t = L2->head->next; //一开始,t 指向 L2第一个节点
L2->head->next = L2->head->next->next; //取出第一个节点,第二个节点变成第一个节点
t->next = p->next; //t 插入 p
p->next = t->next;
p = p->next->next; //移动 p 到下一个待插入的节点
}
}

简单的图示:

图示


算法学习1:重新排序链表

本文原创自http://laker.me/blog,转载请注明出处,欢迎交换友链

如果本文对您有帮助,微信扫一扫,请我吃个鸡腿吧

评论组件不稳定,有事请联系V信 lakerHQ (请备注来自博客)