- 利用栈 先进后出 的特点，将链表的结点一个个入栈，然后一个个出栈，出栈的链表组成一个新的链表，这样就可以实现链表的反转了。
/*
struct listnode {
int val;
struct listnode *next;
listnode(int x) :
val(x), next(null) {
}
};*/
class solution {
public:
listnode* reverselist(listnode* phead) {
listnode* nhead = nullptr;
//判断头结点是否为空
while(phead != nullptr) //每次在新链表的首部插入原链表的首结点
{
//不断将原链表的结点从头插入新链表
listnode* temp = nhead;
nhead = phead;
phead = phead->next;
nhead->next = temp;
}
return nhead;
}
};
- 使用递归函数，一直递归到链表的最后一个结点，最后结点就是反转后的头结点，记作 ans
- 每次函数在返回的过程中，让当前结点的下一个结点的 next 指针指向当前节点
- 同时 让 当前结点的 next 指针指向null ，从而实现从链表尾部开始的局部反转
- 当递归函数全部出栈后，链表反转完成
/*
struct listnode {
int val;
struct listnode *next;
listnode(int x) :
val(x), next(null) {
}
};*/
class solution {
public:
listnode* reverselist(listnode* phead) {
if(phead == null || phead->next == null)
{
return phead;
}
//递归调用
listnode* ans = reverselist(phead->next);
//让当前结点的下一个结点的next指针指向当前节点
phead->next->next = phead;
phead->next = null;
return ans;
}
};
复杂度分析：
- 时间复杂度：o(n)，其中 n 是链表的长度，需要对链表的每个节点进行反转操作
- 空间复杂度：o(n)，其中 n 是链表的长度，空间复杂度主要取决于递归调用的栈空间，最多为 n 层