链表翻转
1、迭代
class Solution {
public:
ListNode* reverseList(ListNode* head) { // 迭代
ListNode* pre = nullptr, * cur = head, * next;
while (cur)
{
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
};
next指针用于保存后续结点,指向交换交给pre、cur指针完成。
2、递归
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head==nullptr || head->next==nullptr) //没有元素或只有一个元素
return head;
ListNode *newhead = reverseList(head->next);
head->next->next = head;
head->next=nullptr;
return newhead;
}
};