# 题目
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
# 递归
路漫漫我不畏
- 使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点，记作 cur
- 此后，每次函数在返回的过程中，让当前结点的下一个结点的 next 指针指向当前节点
- 同时让当前结点的 next 指针指向 NULL ，从而实现从链表尾部开始的局部反转
- 当递归函数全部出栈后，链表反转完成
class Solution | |
{ | |
public: | |
ListNode *reverseList(ListNode *head) | |
{ | |
if (head == NULL || head->next == NULL) | |
{ | |
return head; | |
} | |
ListNode *cur = reverseList(head->next); | |
head->next->next = head; | |
head->next = NULL; | |
return cur; | |
} | |
}; |
# 简单的双指针
- 定义双指针：pre 和 cur
- 局部反转：pre->next=cur
- pre 和 cur 同时右移一个位置
- 循环上述过程，直至 pre 到达链表尾部
class Solution | |
{ | |
public: | |
ListNode *reverseList(ListNode *head) | |
{ | |
ListNode *cur = NULL, *pre = head; | |
while (pre != NULL) | |
{ | |
ListNode *tmp = pre->next; | |
pre->next = cur; | |
cur = pre; | |
pre = tmp; | |
} | |
return cur; | |
} | |
}; |
# 较复杂的双指针
- 定义指针 cur ，初始化为 head
- 局部反转：head->next 的 next 指向 cur
- cur 和 head->next 同时右移一个位置
- 循环上述过程，直至 cur 到达链表尾部
class Solution | |
{ | |
public: | |
ListNode *reverseList(ListNode *head) | |
{ | |
if (head == NULL) | |
{ | |
return NULL; | |
} | |
ListNode *cur = head; | |
while (head->next != NULL) | |
{ | |
ListNode *t = head->next->next; | |
head->next->next = cur; | |
cur = head->next; | |
head->next = t; | |
} | |
return cur; | |
} | |
}; |
