剑指offer No.15 反转链表
一、题目描述
输入一个链表，反转链表后，输出新链表的表头。
示例1
输入：
{1,2,3}返回值：
{3,2,1}二、解题思路
思路一：递归
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
if(pHead==nullptr||pHead->next==nullptr){
return pHead;
}
ListNode* newlist=ReverseList(pHead->next);
pHead->next->next=pHead;
pHead->next=nullptr;
return newlist;
}
};思路二：遍历
初始化：3个指针 1）pre指针指向已经反转好的链表的最后一个节点，最开始没有反转，所以指向nullptr 2）current指针指向待反转链表的第一个节点，最开始第一个节点待反转，所以指向head 3）nextnode指针指向待反转链表的第二个节点，目的是保存链表，因为cur改变指向后，后面的链表则失效了，所以需要保存 接下来，循环执行以下三个操作 1）nextnode = current->next, 保存作用 2）current->next = pre 未反转链表的第一个节点的下个指针指向已反转链表的最后一个节点 3）pre = current， current = nextnode; 指针后移，操作下一个未反转链表的第一个节点 循环条件，当然是current != nullptr 循环结束后，current当然为nullptr，所以返回pre，即为反转后的头结点
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* ReverseList(ListNode* pHead) {
ListNode *pre=NULL;
ListNode *current=pHead;
while(current!=NULL){
ListNode *nextNode=current->next;
current->next=pre;
pre=current;
current=nextNode;
}
return pre;
}
};三、复杂度分析
时间复杂度：O(n), 遍历一次链表 空间复杂度：O(1)
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-11-13，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录