无环单链表的反转

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;
}  

总结

•  感觉这些方法真是太牛逼了，都很精妙，各种实现方式也是很牛逼。最后一种递归的方法也是很赞。保存着每一次调用的地址，在递归进行回溯的时候再使用。牛逼。