【leetcode100-031】【链表】k个一组翻转链表

发布时间:2024年01月05日

【题干】

给你链表的头节点?head?,每?k?个节点一组进行翻转,请你返回修改后的链表。

k?是一个正整数,它的值小于或等于链表的长度。如果节点总数不是?k?的整数倍,那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。

【思路】

  • 非递归折腾一早上了都超时,写个递归版吧
  • 拿到一条链表,我们可以将其分为已处理部分,正在处理部分,待处理部分;
  • 我们每次从待处理部分取出一组k个节点(若还够取),更新待处理部分的起始位置(下一层递归的传入参数),进行处理,并把处理完的结果接到已处理部分的尾部(递归主体),直到待处理部分已不足k个(递归出口);
  • 本题有大量细节需要处理,每一个指针变动都要小心丢链~

【题解】

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        if (head == NULL) return NULL;
        ListNode *a = head;
        ListNode *b = head;
        for (int i = 0; i < k; i++) {
            if (b == NULL) return head;
            b = b->next;
        }

        ListNode *newNode = reverseOperator(a,b);
        a->next = reverseKGroup(b,k);
        return newNode;
    }

    ListNode* reverseOperator(ListNode* n,ListNode *b) {
        ListNode *pre, *cur, *nxt;
        pre = NULL; cur = n; nxt = n;
        while (cur != b) {
            nxt = cur->next;
            cur->next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
};

文章来源:https://blog.csdn.net/weixin_63059689/article/details/135414023
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。