描述
给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。
数据范围： 0≤n≤1000
要求：空间复杂度 O(1) ，时间复杂度 O(n) 。
如当输入链表{1,2,3}时，
经反转后，原链表变为{3,2,1}，所以对应的输出为{3,2,1}。
以上转换过程如下图所示：
基础数据结构知识回顾
空间复杂度 O (1) 表示算法执行所需要的临时空间不随着某个变量 n 的大小而变化，即此算法空间复杂度为一个常量，可表示为 O (1)。例如，下面的代码中，变量 i、j、m 所分配的空间都不随着 n 的变化而变化，因此它的空间复杂度是 O (1)。
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;时间复杂度 O (n) 表示算法执行的时间与 n 成正比，即此算法时间复杂度为线性阶，可表示为 O (n)。例如，下面的代码中，for 循环里面的代码会执行 n 遍，因此它消耗的时间是随着 n 的变化而变化的，因此这类代码都可以用 O (n) 来表示它的时间复杂度。
for (i=1; i<=n; ++i)
{
j = i;
j++;
}题解C++篇
可以先用一个vector将单链表的指针都存起来，然后再构造链表。
此方法简单易懂，代码好些。
// 定义一个Solution类
class Solution {
public:
// 定义一个函数，接收一个链表的头节点指针，返回一个反转后的链表的头节点指针
ListNode* ReverseList(ListNode* pHead) {
// 如果头节点指针为空，直接返回空指针
if (!pHead) return nullptr;
// 定义一个vector，用于存储链表中的每个节点指针
vector<ListNode*> v;
// 遍历链表，将每个节点指针放入vector中
while (pHead) {
v.push_back(pHead);
pHead = pHead->next;
}
// 反转vector，也可以逆向遍历
reverse(v.begin(), v.end());
// 取出vector中的第一个元素，作为反转后的链表的头节点指针
ListNode *head = v[0];
// 定义一个当前节点指针，初始化为头节点指针
ListNode *cur = head;
// 从第二个元素开始遍历vector，构造反转后的链表
for (int i=1; i<v.size(); ++i) {
// 当前节点的下一个指针指向下一个节点
cur->next = v[i];
// 当前节点后移
cur = cur->next;
}
// 切记最后一个节点的下一个指针指向nullptr
cur->next = nullptr;
// 返回反转后的链表的头节点指针
return head;
}
};初始化：3个指针
1）pre指针指向已经反转好的链表的最后一个节点，最开始没有反转，所以指向nullptr
2）cur指针指向待反转链表的第一个节点，最开始第一个节点待反转，所以指向head
3）nex指针指向待反转链表的第二个节点，目的是保存链表，因为cur改变指向后，后面的链表则失效了，所以需要保存
接下来，循环执行以下三个操作
1）nex = cur->next, 保存作用
2）cur->next = pre 未反转链表的第一个节点的下个指针指向已反转链表的最后一个节点
3）pre = cur， cur = nex; 指针后移，操作下一个未反转链表的第一个节点
循环条件，当然是cur != nullptr
循环结束后，cur当然为nullptr，所以返回pre，即为反转后的头结点
这里以1->2->3->4->5 举例：
// 定义一个Solution类
class Solution {
public:
// 定义一个函数，接收一个链表的头节点指针，返回一个反转后的链表的头节点指针
ListNode* ReverseList(ListNode* pHead) {
// 定义一个前驱节点指针，初始化为nullptr
ListNode *pre = nullptr;
// 定义一个当前节点指针，初始化为头节点指针
ListNode *cur = pHead;
// 定义一个后继节点指针，初始化为nullptr
ListNode *nex = nullptr;
// 遍历链表，反转每个节点的指向
while (cur) {
// 记录当前节点的下一个节点
nex = cur->next;
// 将当前节点的下一个指针指向前驱节点
cur->next = pre;
// 将前驱节点更新为当前节点
pre = cur;
// 将当前节点更新为后继节点
cur = nex;
}
// 返回反转后的链表的头节点指针，即原链表的尾节点指针
return pre;
}
};题解Python篇
假设 链表为 1->2->3->4->null 空就是链表的尾
obj： 4->3->2->1->null
那么逻辑是
首先设定待反转链表的尾 pre = none
head 代表一个动态的表头 逐步取下一次链表的值
然后利用temp保存 head.next 第一次迭代head为1 temp 为2 原始链表中是1->2
现在我们需要翻转 即 令head.next = pre 实现 1->none
但此时链表切断了 变成了 1->none 2->3->4
所以我们要移动指针，另pre = head 也就是pre从none 变成1 下一次即可完成2->1的链接
此外另head = next 也就是说 把指针移动到后面仍然链接的链表上
这样执行下一次循环 则实现 把2->3 转变为 2->1->none
然后再次迭代
直到最后一次 head 变成了none 而pre变成了4 则pre是新的链表的表头
完成翻转
# -*- coding:utf-8 -*-
# 定义一个ListNode类，表示链表中的节点
# class ListNode:
# def __init__(self, x):
# self.val = x # 节点的值
# self.next = None # 节点的下一个指针
# 定义一个Solution类，用于解决问题
class Solution:
# 定义一个函数，接收一个链表的头节点，返回一个反转后的链表的头节点
def ReverseList(self, pHead):
# write code here
pre = None # 定义一个前驱节点，初始化为None
head = pHead # 定义一个当前节点，初始化为头节点
while head: # 遍历链表，反转每个节点的指向
temp = head.next # 记录当前节点的下一个节点
head.next = pre # 将当前节点的下一个指针指向前驱节点
pre = head # 将前驱节点更新为当前节点
head = temp # 将当前节点更新为下一个节点
return pre # 返回反转后的链表的头节点，即原链表的尾节点
评论 (0)