给定单链表的头节点 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
进阶:链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题?
初始代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
}
};
解题思路
受不了了,一拳把链表打爆
又写了遍这题感受了下。发现不太好理解的地方是为什么要新建一个tmp节点,而只有返回的时候用到了tmp节点。
栈顶tmp节点保存的是节点的地址。因为每次递归返回时都对tmp的上一个节点(将其next指针置空)和下一个节点(将其next指针指向tmp的上一个节点)进行操作,唯独不需要更改tmp节点本身。为了更改next后不丢失该节点的地址,所以将其作为返回值。
当然此时还返回head是不行的。head在每次的递归弹出栈的那个过程中,每次都被更改为了新的尾节点。所以你返回head的话最后返回的是反转链表的尾节点。
完整代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(head==NULL||head->next==NULL)
return head;
ListNode*tmp=reverseList(head->next);
head->next->next=head;
head->next=NULL;
return tmp;
}
};