AcWing 35. 反转链表
原题链接
简单
作者:
动力春风
,
2021-07-27 16:16:52
,
所有人可见
,
阅读 234
迭代
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode* pre = NULL, *cur = head, *next = cur;
while (cur) {
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
};
递归
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
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;
}
};