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

牛群的重新分组

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

一、知识点:

链表、链表反转

二、文字分析:

  1. 创建一个虚拟头节点dummy,将其指向原链表的头节点head
  2. 计算链表的长度length,以便确定需要进行翻转的组数。
  3. 初始化两个指针prevcurr,分别指向当前组的前一个节点和当前组的第一个节点。
  4. 在每一组内,使用反转操作将节点的指针方向翻转。
  5. 连接相邻的组。
  6. 返回虚拟头节点的next指针。

计算链表的长度,所以时间复杂度为O(n),其中n是链表的长度。接下来,每次翻转k个节点需要进行k-1次节点交换,因此每个节点只会被访问一次,总的时间复杂度为O(n)。由于只使用了常数级别的额外空间,所以空间复杂度为O(1)。

三、编程语言:

java

四、正确代码:

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 length = 0;
        while (head != null) {
            length++;
            head = head.next;
        }

        for (int i = 0; i < length / k; i++) {
            for (int j = 1; j < k; j++) {
                ListNode next = curr.next;
                curr.next = next.next;
                next.next = prev.next;
                prev.next = next;
            }
            prev = curr;
            curr = curr.next;
        }

        return dummy.next;
    }
}

全部评论
牛,这怎么想到的,绕来绕去看答案我都很难吃得消
1 回复 分享
发布于 2023-07-25 21:57 四川

相关推荐

04-29 18:07
常州大学 Java
寂静羽翼:兄弟我已经亲身经历了,双非没实习很多大厂还是会给笔试的,可是有的公司笔试做的好也不给面一直卡着,ssob基本看我没实习都拒绝我了,但是每天投满偶尔也能有一两场初创公司的面试,但是薪资基本在五六千
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

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