AcWing 35. 反转链表
原题链接
简单
作者:
andream7
,
2020-12-23 14:59:08
,
所有人可见
,
阅读 314
- 迭代
翻转即所有节点的指针指向前驱,头节点没有前驱所以有加一个pre指针指向头节点,同时需要next指针记录后继
/**
* 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 = nullptr;
auto cur = head;
while(cur) {
auto next = cur->next;
cur->next = pre;
// pre后移到cur的位置
pre = cur;
// cur 后移到next的位置
cur = next;
}
return pre;
}
};
- 递归
递归翻转head->next, 反转之后这部分的头节点就是tail, 这部分的尾就是head->next, 再把head接到反转后这部分的末尾,同时head->next置为空。
/**
* 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;
// 原来的链表尾成为了链表头, head->next翻转后成为链表尾
auto tail = reverseList(head->next);
// 把head接到链表尾的next后面
head->next->next = head;
// 尾节点的next置空
head->next = NULL;
// 返回新的头节点
return tail;
}
};