数据结构 -- 链表 -- 链表反转_数据结构链表数据反转

今天在牛客网上玩了一下刷题，尝试了一下链表反转，有些思路借此记录一下；

题目是这样子的：

        一开始，没有什么好的思路，毕竟数据结构也有一段时间没有接触，大概思考了一点时间，有了下面的第一个思路：生成一个新的节点A，保存链表节点1的value，然后继续生成节点B，保存A的地址以及节点2的value；依次生成节点与复制数据，不就完成了这个动作，后来想了一下，那我原来的链表还要释放，好家伙，又需要遍历一次链表，哪个少年能接受这种做法，我这种方法肯定不是最优的，但绝对是最笨的实现；

        后来，琢磨了一下子后，突然想到链表不就是根据节点里的地址找到下一个节点的吗，那我直接搞这个数据，把他修改为上一个节点的地址，这样依次修改，最终不就完成链表的反转；

于是，第一份代码出来了：

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
 
/**
 * 
 * @param pHead ListNode类 
 * @return ListNode类
 */
struct ListNode* ReverseList(struct ListNode* pHead ) {
    // write code here
    struct ListNode* pListNodePre = pHead, *pListNodeCur,*pListNodeNext;
    if(pHead == NULL)
        return NULL;
    pListNodeCur = pListNodePre->next;
    pListNodePre->next = NULL;
    
    while(pListNodeCur)
    {
        pListNodeNext = pListNodeCur->next;
        pListNodeCur->next = pListNodePre;
        pListNodePre = pListNodeCur;
        pListNodeCur = pListNodeNext;
    }
    return pListNodePre;
}

然后，发现代码运行占用的空间竟然比前辈们的大，仔细研究了与前辈的代码差别后，整出来了V2.0的版本，就是把中间的赋值表达式去掉了，然后，将pHead由原来赋值给pListNodePre修改为赋值给pListNodeCur；

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
 
/**
 * 
 * @param pHead ListNode类 
 * @return ListNode类
 */
struct ListNode* ReverseList(struct ListNode* pHead ) {
    // write code here
    struct ListNode* pListNodePre = NULL, *pListNodeCur = pHead,*pListNodeNext;
    if(pHead == NULL || pHead->next == NULL)
        return pHead;
    
    while(pListNodeCur)
    {
        pListNodeNext = pListNodeCur->next;
        pListNodeCur->next = pListNodePre;
        pListNodePre = pListNodeCur;
        pListNodeCur = pListNodeNext;
    }
    return pListNodePre;
}