LCR 141. 训练计划 III

Leetcode题目:链表的递归和迭代

给定一个头节点为 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;
    }
};
Subscribe
提醒
0 评论
Inline Feedbacks
View all comments
0
在此留下你的评论x