无环单链表的反转
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;
}
总结
感觉这些方法真是太牛逼了，都很精妙，各种实现方式也是很牛逼。最后一种递归的方法也是很赞。保存着每一次调用的地址，在递归进行回溯的时候再使用。牛逼。
