方法一:使用栈解决
- 利用栈 先进后出 的特点,将链表的结点一个个入栈,然后一个个出栈,出栈的链表组成一个新的链表,这样就可以实现链表的反转了。
/*
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 层