专栏首页刷题笔记【LeetCode每日打卡】25. Reverse Nodes in k-Group

【LeetCode每日打卡】25. Reverse Nodes in k-Group

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

k is a positive integer and is less than or equal to the length of the linked list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

Example:

Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Note:

Only constant extra memory is allowed. You may not alter the values in the list's nodes, only nodes itself may be changed.

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/reverse-nodes-in-k-group 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

链表每K个元素进行翻转

拆成链表翻转 + k个链表链接即可

reverse方法抽取出来进行翻转

while (end.next != null) { 翻转能翻转的部分

for (int i = 0; i < k && end != null; i++) end = end.next; if (end == null) break; 判断是否可以翻转

头尾记录后开始进行翻转。

ListNode start = pre.next; ListNode next = end.next; end.next = null; pre.next = reverse(start); start.next = next; pre = start;

end = pre;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    ListNode pre = dummy;
    ListNode end = dummy;

    while (end.next != null) {
        for (int i = 0; i < k && end != null; i++) end = end.next;
        if (end == null) break;
        ListNode start = pre.next;
        ListNode next = end.next;
        end.next = null;
        pre.next = reverse(start);
        start.next = next;
        pre = start;

        end = pre;
    }
    return dummy.next;
}

private ListNode reverse(ListNode head) {
    ListNode pre = null;
    ListNode curr = head;
    while (curr != null) {
        ListNode next = curr.next;
        curr.next = pre;
        pre = curr;
        curr = next;
    }
    return pre;
}

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【LeetCode】148. 排序链表

    你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?

    韩旭051
  • 【Leet Code】19. Remove Nth Node From End of List

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    韩旭051
  • 【LeetCode】23. Merge k Sorted Lists 分治

    Merge k sorted linked lists and return it as one sorted list. Analyze and descri...

    韩旭051
  • JS数据结构第二篇---链表

    链表是一种链式存储的线性表,是由一组节点组成的集合,每一个节点都存储了下一个节点的地址;指向另一个节点的引用叫链;和数组中的元素内存地址是连续的相比,链表中的所...

    tandaxia
  • 面试必备 | 不可不会的反转链表

    反转链表这题真的是面试非常喜欢考的了,这题看起来简单,但是能用两种方法一遍 bug free 也是不容易的,面试的时候可以筛下来一大批人,无论是对 junior...

    敖丙
  • 【LeetCode】148. 排序链表

    你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?

    韩旭051
  • [Leetcode][python]Swap Nodes in Pairs/两两交换链表中的节点

    交换链表中相邻的两个元素。 注意第一个节点与第二个节点要交换位置,而第二个节点不用与第三个节点交换位置。 注意点: 不允许修改节点的值 ...

    后端技术漫谈
  • 模式匹配KMP算法

    匹配到j=5时失效了,BF算法里我们会使i=1,j=0,再看s的第i位开始能不能匹配,而KMP算法接下来就去比较T[2](next[5]=2)和S[5]

    饶文津
  • leetcode:83 删除排序链表中的重复元素

    问题? 如果next没有值的话,会报错的。 因为要相等啊,比较啊,有值才能比较是吧。 那为什么p.next=p.next.next;如果p.next.ne...

    用户7873631
  • 【玩转腾讯云】python next函数

    python 3.x内置函数next可以从迭代器中检索下一个元素或者数据,可以用于迭代器遍历,使用的时候注意会触发 StopIteration 异常!

    猿说编程[Python和C]

扫码关注云+社区

领取腾讯云代金券