题目描述
定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。
样例
输入
1->2->3->4->5->NULL
输出
5->4->3->2->1->NULL
算法1 迭代法
$O(n)$
使用三个指针,cur指向当前节点,pre是当前节点的前一个节点,next是cur的下一个节点。
初始时,cur为头节点,pre为空指针。
从头节点开始遍历,直到链表为空。
每遍历到一个节点,就记录一下当前节点的下一个节点,记作next。然后将当前节点的next指针指向当前节点的前一个节点(pre)。之后更新pre跟cur指针。
时间复杂度
只需一次遍历,时间复杂度为$O(n)$
空间复杂度
只有三个额外的变量,空间复杂度为$O(1)$
C++ 代码
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *cur=head, *pre=NULL;
while(cur!=NULL){
ListNode *next = cur->next;
cur->next=pre;
pre=cur;
cur=next;
}
return pre;
}
};
算法2 递归法
$O(n)$
首先明确一点,reverseList该函数的输入是一个链表的头节点,输出是将这个链表反转之后的新的头节点,也就是原来链表的尾节点。
其次明确递归出口和递归表达式。
递归出口为当头节点为空或者头节点的next指针为空时,直接返回头节点。
递归表达式如代码所示。
时间复杂度
链表中的每个节点只会被遍历一次,所以时间复杂度是$O(n)$
空间复杂度
总共递归n层,系统栈的空间复杂度为$O(n)$
C++ 代码
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(!head||!head->next) return head;
ListNode *tail = reverseList(head->next);
head->next->next=head;
head->next=NULL;
return tail;
}
};