给你单链表的头节点 head ,请你反转链表,并返回反转后的链表。
示例 1:
输入:head = [1,2,3,4,5]
输出:[5,4,3,2,1]
示例 2:
输入:head = [1,2]
输出:[2,1]
示例 3:
输入:head = []
输出:[]
提示:
链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000 进阶:链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题?
解题思路:
此题一般常用的方法有两种,三指针翻转法和头插法
- 三指针翻转法
记录连续的三个节点,原地修改节点指向 - 头插法
每一个节点都进行头插
解法一
使用三个指针
- 初始条件:n1 = NULL; n2 = head; n3 = head->next
- 核心逻辑:n2->next = n1
- 迭代条件
- 结束条件: n2 = NULL
demo
struct ListNode* reverseList(struct ListNode* head){
if(head == NULL || head->next == NULL) {
return head;
}
struct ListNode* n1 = NULL, *n2 = head, *n3 = head->next;
while(n2 != NULL) {
//核心逻辑
n2->next = n1;
//迭代
n1 = n2;
n2 = n3;
if(n3 != NULL)
n3 = n3->next;
}
return n1;
}
注意点:
对特殊情况判断,head == NULL
要在前面,这和 || 符号的运算规则有关。
解法二
取原链表的结点插入到newhead的新链表中。(不带头结点的情况)
struct ListNode* reverseList(struct ListNode* head){
struct ListNode* newhead = NULL, *n1 = head;
while(n1) {
// 核心逻辑
struct ListNode* n2 = n1->next;
n1->next = newhead;
// 迭代
newhead = n1;
n1 = n2;
if(n2 != NULL)
n2 = n2->next;
}
return newhead;
}