题解 | #链表中的节点每k个一组翻转#

链表中的节点每k个一组翻转

http://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e

思路

正序,即从前往后按步长k遍历并翻转,然后每个子链表首尾拼接; 即:

  1. 如何链表长度<2,则直接返回;
  2. 定义全局变量节点:curr,用来记录当前要执行反转的开始开始位置节点;然后逐个k长子链翻转,最后用递归从后向前首尾链接;
  • 定义计数值i = 0, 然后从curr节点开始,逐个节点前后翻转,翻转的子链表长度为k;
  • 当 i == k 或者 curr == nullptr 时,退出子翻转,保存子链表翻转后的头结点:prev; 此时curr变量已更新为下一个要翻转子链的开始节点;
  • 让该子链表的尾节点的next节点指向下一个翻转好的子节点的头结点;因此最后一步用到递归,实现从后向前逐段子链首尾链接;
  • 若最后一段子链长度<k, 则将其再次翻转为正序并返回;
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

class Solution {
public:
    /**
     * 
     * @param head ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    ListNode* curr; //定义全局变量节点:curr,用来记录当前要执行反转的开始开始位置节点;
    bool start = true;
    ListNode* reverseKGroup(ListNode* head, int k) {
        // write code here
        if(!head || !head->next || k < 2) {
            return head;
        }
        return reverse_List(head, k);
    }
    //从curr节点开始,逐个节点前后翻转,翻转的子链表长度为k
    ListNode* reverse_List(ListNode* head, int k) {
        if(!head) {
            return nullptr;
        }
        curr = head;
        ListNode* prev = nullptr;
        int i = 0;
        while (curr && i < k) {
            ListNode* rear = curr->next;
            curr->next = prev;
            prev = curr;
            curr = rear;
            ++i;
        }
        // 若最后一段子链长度<k, 则将其再次翻转为正序并返回;
        if(i > 0 && i < k) {
            return reverse_SubList(prev, i);
        } 
        // 让该子链表的尾节点的next节点指向下一个翻转好的子节点的头结点;因此最后一步用到递归
        head->next = reverse_List(curr, k);
        return prev;
    }
    
    ListNode* reverse_SubList(ListNode *head, int k) {
        ListNode* cur = head;
        ListNode* prev = nullptr;
        while(cur && k--) {
            ListNode* next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        return prev;
    }
};
全部评论
厉害了,我的前辈
点赞 回复 分享
发布于 2022-10-21 21:31 陕西

相关推荐

06-12 17:46
门头沟学院 Java
运营你豪哥:来说重点: ​1.项目前置,时间倒序。​​ 2.​项目描述强化结果与量化效果(STAR原则里的R)。​​ ​3.个人技能精炼,明确掌握程度,突出核心。​​ ​4.增加强有力开头的个人总结部分。​​ 5.​优化教育背景(成绩排名)、合并奖项与活动。​​
听劝,我这个简历该怎么改...
点赞 评论 收藏
分享
07-21 18:43
门头沟学院 Java
是暑期都招满了吗
ANEOY:今年感觉真是后端地狱级难度了,从暑期就是这样,前端需求非常大
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务