题解 | #牛群的重新分组#

牛群的重新分组

https://www.nowcoder.com/practice/267c0deb9a6a41e4bdeb1b2addc64c93

首先写个函数,函数输入值为操作区间的前一个节点,和操作区间的后一个节点。

主函数里构造虚拟头结点为初始prev,初始curr指向head。用count++计数,不能整除k就curr后移一位,能整除就带入函数操作,再更新prev和curr指针。

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {

    public ListNode reverseKGroup (ListNode head, int k) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode prev = dummy;
        ListNode curr = head;

        int count = 0;
        while (curr != null) {
            count++;
            if (count % k == 0) {
                prev = reverse(prev, curr.next);
                curr = prev.next;
            } else {
                curr = curr.next;
            }
        }

        return dummy.next;
    }
    ListNode reverse(ListNode prev, ListNode end) {
        ListNode curr = prev.next;
        ListNode tail = curr;

        while (curr != end) {
            ListNode temp = curr.next;
            curr.next = prev.next;
            prev.next = curr;
            curr = temp;
        }

        tail.next = end;
        return tail;
    }
}

算法题刷刷刷 文章被收录于专栏

数组、链表、栈、队列、堆、树、图等。 查找和排序:二分查找、线性查找、快速排序、归并排序、堆排序等。 动态规划:背包问题、最长公共子序列、最短路径 贪心算法:活动选择、霍夫曼编码 图:深度优先搜索、广度优先搜索、拓扑排序、最短路径算法(如 Dijkstra、Floyd-Warshall) 字符串操作:KMP 算法、正则表达式匹配 回溯算法:八皇后问题、0-1 背包问题 分治算法:归并排序、快速排序

全部评论
cur->next = prev->next; prev->next = cur; cur = tmp; 这一部分理解不了
点赞 回复 分享
发布于 2023-08-08 22:15 山东

相关推荐

Debug_EVE:简历不要做成左右两页的,尽量做成上下一页
点赞 评论 收藏
分享
评论
5
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务