题解 | #反转链表#
反转链表
http://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca
描述
这是一篇面对初级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
总结
各位牛友在练习的时候要注意边界条件的判定
扩展
快慢指针是链表中一种常见的处理方法
在判断链表中是否有环中也很有用
阿Q的题解 文章被收录于专栏
阿Q秋招刷过的题
