反转链表

题目：

给定一个单链表的头结点pHead，长度为n，反转该链表后，返回新链表的表头。
 
数据范围： nleq1000n≤1000
要求：空间复杂度 O(1)O(1) ，时间复杂度 O(n)O(n) 。
 
如当输入链表{1,2,3}时，
经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。

题目的意思很好理解，就是按照相反的顺序输出一个链表。

这道题有两种思路，第一种很简单，就是先便利一遍链表，并把数存一下，然后再新建一个链表，将对应的数插进去，再返回新建链表的头指针即可。

第二种思路是在原链表的基础上，改变链表的指向。

首先看第一种方法：

struct ListNode* ReverseList(struct ListNode* pHead ) {
    // write code here
    int n=0;
    int a[1000];
    struct ListNode* Head;
    Head=(struct ListNode*)malloc(sizeof(struct ListNode));
    while(pHead!=NULL){
        a[n]=pHead->val;
        ++n;
        pHead=pHead->next;   
    }
    struct ListNode *end,*node;
    end=Head;
    for(int i=0;i<n;++i){
        node=(struct ListNode*)malloc(sizeof(struct ListNode));
        node->val=a[n-1-i];
        end->next=node;
        end=node;
    }
    end->next=NULL;
    return Head->next;
}

 C的代码附在上面了，这个还是比较好理解的哈！

官方的题解上面给的C++写法跟这个差不多，不过它用的是vector，差不多的意思。

第二种方法：

先看代码吧：

struct ListNode* ReverseList(struct ListNode* pHead ) {
    // write code here
    
    struct ListNode* node,* end;
    end=NULL; //待反转的结点
    node=pHead; //作为反转后的头结点
    while(node->next){//如果下一跳是null，说明反转结束了
        pHead=node->next; //首先保证待反转的结点和后面的结点“联系不能断”
        node->next=end; //反转
        end=node; //往后传递待反转的结点
        node=pHead; 
    }
//循环结束后，node结点指向的是反向结点的头。但是经过上述循环后，反向的第一个结点和第二个结点之间并未建立联系，所以有下面的操作
    pHead=node;
    pHead->next=end;
    return pHead;
}

------------------------------------------------------------

上述第二种方法的代码可以过样例，但是提交则显示段错误，后经检查，发现如果输入的是一个空链表的话，会出现找不到指针的问题，所以更改后的代码如下下：

struct ListNode* ReverseList(struct ListNode* pHead ) {
    // write code here
    struct ListNode* node,* end;
    end=NULL;
    node=pHead;
    while(node){
        pHead=node->next;
        node->next=end;
        end=node;
        node=pHead;
    } 
    return end;
}

两种方法都很好理解，这一题也是一道基础题。

 （点点关注和赞吧各位大佬）