无环单链表的反转
http://blog.csdn.net/feliciafay/article/details/6841115
超经典
方法一:新创建一个单链表
- 优点:此方法很简单,利用单链表的头插法即可
- 缺点:多创建了一张表耗费内存空间
-实现关键:遍历原链表,创建新链表,新链表使用头插法进行创建
具体代码:
LinkList p = (LinkList)malloc(sizeof(node));
p->next = nill;
while(p1){//原链表的只一个节点
//创建一个新节点
LinkList q = (LinkList)malloc(sizeof(node));
q->data = p1->data;
//头插法直接实现链表的反转
q->next = p->next;
p->next = q;
p1 = p1->next;
}
方法二:循环顺序反转
- 优点:不用开辟新的空间,只需要3个指针变量就行
- 缺点:实现较复杂
- 实现关键:这种也是一种遍历的反转方式,主要是要一个用于循环的指针p,以及一个指针q,用于表示p的前一个节点,另外还需要一个指针用于存储p的下一个节点
实现代码
LinkList p = head->next->next;
LinkList q = head->next;
LinkList r;
while(p){
//利用中间指针变量对指针p的下一个节点的位置进行存储
r = p->next;
p->next = q;
q = p;
p = r;
}
head = q;
image.png
方法三:同样是循环遍历的一种反转方式
- 优点:优点在于这种实现的方式更加的省指针,不需要中间的指针,将头指针作为中转指针
- 缺点:逻辑更复杂
- 实现关键: 实现的关键在于换掉节点间的逻辑关系
实现代码
Linklist p = head->next;
Linklist q;
while(p->next != null){
q = p->next;
p->next = q->next;
q->next = head->next;
head->next = q;
}
//当p后没有节点时,将原来的头节点链接过来
p->next = head;
head = p->next->next;
p->next->next = null;
方法四: 递归实现
- 优点:想法简单
- 缺点:递归的通病就在于耗费内存空间,每递归一次操作系统都将把当前的上下文压栈,因此递归的次数越多耗费的内存将越多
- 实现关键: 实现的关键在将问题进行划分,将大问题划分为多个子问题,但递归存在很多重复子问题,这也是为什么递归耗时的原因。递归的结束条件就是最后一个节点一经被反转
LinkList revers(LinkList head,LinkList & new_head){
if(head = null){
return;
}
if(head->next = null){
new_head = head;
return head;
}
LinkList new_Tail = LinkList revers(head->next , new_head);
//完成反向操作
new_Tail ->next = head;
//断开连接
head->next = null;
//返回当前的指针节点
return head;
}
总结
感觉这些方法真是太牛逼了,都很精妙,各种实现方式也是很牛逼。最后一种递归的方法也是很赞。保存着每一次调用的地址,在递归进行回溯的时候再使用。牛逼。
网友评论