AcWing 35. 反转链表
原题链接
简单
作者:
术
,
2020-12-23 12:01:49
,
所有人可见
,
阅读 382
class Solution {
public:
//空间复杂度1 时间n
/*ListNode* reverseList(ListNode* head) {
ListNode *pre=nullptr;
//1.每次都使当前结点指向前驱结点!!!!
//最后的尾结点设为null
ListNode *cur=head;
while(cur){
ListNode *r=cur->next;//暂存一下q->next;
cur->next=pre;
pre=cur;
cur=r;
}
return pre;
}*/
/*ListNode* reverseList(ListNode* head) {
ListNode *p,*q;
p=head;
q=p->next;
while(q){//这里是判断第二个结点
ListNode *r=q->next;//这里记录第三个结点(因为下一语句把第三个覆盖了)!!! 每次迭代完变量自动销毁
q->next=p;
p=q;
q=r;
}
head->next=nullptr;
//尾结点的next要设为空(由于head的next指向还为2,需要设空),但是尾结点不能设空
return p;
}*/
//递归! 空间复杂度n 时间n
ListNode* reverseList(ListNode* head) {
if(!head||!head->next) return head;
ListNode *tail=reverseList(head->next);
head->next->next=head;//将新链表的尾结点指向head
head->next=nullptr;
return tail;;
}
};