描述

这是一篇面对初级coder的题解。
知识点：链表 栈
难度：一星

题解

题目：输入一个链表，反转链表后，输出新链表的表头。

考察链表的基础知识

方法一：栈

利用栈后进先出的特性，可以实现链表翻转 

#includeclass Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
        stack<listnode> stack;//栈
        ListNode *answer=NULL;//返回值
        if(!pHead)
            return pHead;
        while(pHead->next)//全部入栈
        {
            stack.push(pHead);
            pHead=pHead->next;
        }
        answer = pHead;
        for(int k=stack.size(); k>0;k--)
        {
            pHead->next=stack.top();
            stack.pop();
            pHead=pHead->next;
        }
        pHead->next = nullptr;//尾指针置空 避免回环
        return answer;
    }
};</listnode>


运行时间 6ms  占用内存 504KB

方法二：用指针调转

本质上是两个链表，逐个把旧链表的节点调转到新链表下
一个复杂且清晰的版本 
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
    struct ListNode *newnode=NULL; //新节点
    struct ListNode *tempnode;//交换缓存
   if(pHead==NULL)
            return pHead;
    while(pHead->next!=NULL)
    {
        if(newnode == NULL)//第一次进入
        {
            newnode = pHead;//把头结点挪过来
            pHead=pHead->next;
            newnode->next=NULL;
        }
        else
        {
            tempnode=newnode;//利用交换缓存从旧链表取节点，作为新链表头节点
            newnode=pHead;
            pHead=pHead->next;
            newnode->next=tempnode;
        }
    }
        pHead->next=newnode;//把最后一个节点挂上去
        return pHead;
    }
};
运行时间 8ms  占用内存 624KB
进一步优化代码逻辑 
class Solution {
public:
    ListNode* ReverseList(ListNode* pHead) {
    struct ListNode *newnode=NULL; //新链表头指针
    struct ListNode *tempnode;//交换缓存，临时存放要换过来的头节点
    while(pHead)
    {
        tempnode=pHead->next;//利用交换缓存从旧链表取节点，
        pHead->next=newnode;//作为新链表头节点
        newnode=pHead;//更新新链表
        pHead=tempnode;//更新旧链表

    }
    return newnode;//返回新链表
    }
};
运行时间 8ms
占用内存 632KB


总结

各位牛友在练习的时候要注意边界条件的判定

扩展

快慢指针是链表中一种常见的处理方法
在判断链表中是否有环中也很有用