给定一个头节点为 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
解题思路
又是链表反转
在反复练习后,终于搞定了链表反转的大致思路。
先是迭代,不需要想的太复杂。新建一个哑元节点pre,同时它也是最后新的头节点。cur->next=pre,将当前节点的next指针指向其上一个节点。再让pre=cur,移动pre的位置至当前节点。最后再cur=tmp,将cur的位置移到下一个节点。如此迭代,最后返回pre。
完整代码(迭代)
/**
* 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* trainningPlan(ListNode* head) {
ListNode*pre=NULL;
ListNode*cur=head;
while(cur!=NULL)
{
ListNode*tmp=cur->next;
cur->next=pre;
pre=cur;
cur=tmp;
}
return pre;
}
};
接下来是递归。比如1-2-3-4-5,此时head在5位置时就会开往回走。4-5->next指回到4,再将4->next置空。继续回退,再将3->4->next指回到3,将3->next置空。
完整代码(递归)
/**
* 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* trainningPlan(ListNode* head) {
if(head==NULL||head->next==NULL)
return head;
ListNode*newHead=trainningPlan(head->next);
head->next->next=head;
head->next=NULL;
return newHead;
}
};