单链表的反转

方法一：

新建一个单链表，遍历源链表。每次将源链表中的节点插到新链表的第一个节点位置

struct Node 
{
    int data;
    Node * next;
};
//带表头单链表
//新建一个单链表，遍历源链表。每次将源链表中的节点插到新链表的第一个节点位置
Node *  reverselist(Node * list){
    Node *cur,*newList,*tmp;
    cur = list->next;
    newList = new Node;
    newList->next=NULL;
    while (cur!=NULL)
    {
        tmp = new Node;
        tmp->data = cur->data;
        tmp->next = newList->next;
        newList->next = tmp;
        cur = cur->next;
    }
    return newList;
};

 方法二：方法一中是重新构造一个单链表，本方法则直接修改原单链表。

基本思想是每次将第一个节点后面的那个节点放到头结点的后面

 初始状态 ： L  -> 1 -> 2-> 3 -> 4 

 第一趟   ：  L -> 2 ->1 -> 3 -> 4

 第二趟   :    L -> 3 ->2 -> 1 ->4

 第三趟   ：  L ->4 -> 3 -> 2-> 1

void reverList2(Node * list)
{
    Node * firstNode,* tmpNode;
    firstNode = list->next;//记录第一个节点

    while (firstNode->next!=NULL)
    {
        tmpNode = firstNode->next;//要放到头结点后面的节点
        firstNode->next = tmpNode->next;
        tmpNode->next = list->next;
        list->next = tmpNode;//将要交换的节点放到头结点后面
    }

}