超高频面试题,面试官有可能两种都会问,都掌握一下没坏处。
非递归实现
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) return head; //若链表为空或只有一个值,直接返回
auto p1 = head, p2 = p1->next;
while (p2)
{
auto p3 = p2->next;
p2->next = p1; //相当于把'->'变成了'<-'
p1 = p2, p2 = p3;
}
head->next = NULL; //head指针本来指向1,反转后指向NULL
return p1;
}
};
递归实现
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (!head || !head->next) return head;
ListNode* p = reverseList(head->next); //这个p永远表示最后一个节点
head->next->next = head;
head->next = NULL;
return p;
}
};