单链表逆置

明天阿里面,并无卵用的假装复习一下数据结构,总结一下单链表的逆置算法,包括 复制逆置就地逆置

复制逆置

所谓复制逆置,就是再开一个同样的空间,用于存储新的单链表,空间复杂度为O(n)。具体做法:从原链表顺序取元素,采用头插法插入到新的空链表中,完成逆置。

复制逆置没有什么难度,主要考的还是 就地逆置

就地逆置

就地逆置要保证时间复杂度为O(n) && 无辅助空间。总的来说:设置一指针p总是指向第一个结点(即从头到尾都指向的是同一个第一个结点),每次都将p后面的结点用头插法移动到头结点后面,循环就好了。

具体算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef struct LNode {
int data;
struct LNode* next;
} LNode, *LinkList;

void Reverse(LinkList list) {
LinkList p, q; //p总是指向开始就是第一个的结点, q = p->next
if ( list == NULL )
return;

p = list->next; //从下面也可以看出来,p的指针就不再变化了

while ( p->next != NULL ){
q = p->next;
p->next = q->next;
q-next = list->next;
list->next = q;
}
}

参考文章 : pianoid 博客

明天呢,增加下阅历。

个人GitHub: http://github.com/icodeu

CSDN博客:http://blog.csdn.net/icodeyou

个人微信号:qqwanghuan 技术交流

image