原题链接:http://oj.leetcode.com/problems/reverse-nodes-in-k-group/这道题是Swap
Nodes in Pairs的扩展,Swap
Nodes in Pairs其实是这道题k=2的特殊情况,大家可以先练习一下。不过实现起来还是比较不一样的,因为要处理比较general的情形。基本思路是这样的,我们统计目前节点数量,如果到达k,就把当前k个结点reverse,这里需要reverse
linked list的subroutine。这里我们需要先往前走,到达k的时候才做reverse,所以总体来说每个结点会被访问两次。总时间复杂度是O(2*n)=O(n),空间复杂度是O(1)。实现的代码如下:
public ListNode reverseKGroup(ListNode head, int k) {
if(head == null)
{
return null;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
int count = 0;
ListNode pre = dummy;
ListNode cur = head;
while(cur != null)
{
count ++;
ListNode next = cur.next;
if(count == k)
{
pre = reverse(pre, next);
count = 0;
}
cur = next;
}
return dummy.next;
}
private ListNode reverse(ListNode pre, ListNode end)
{
if(pre==null || pre.next==null)
return pre;
ListNode head = pre.next;
ListNode cur = pre.next.next;
while(cur!=end)
{
ListNode next = cur.next;
cur.next = pre.next;
pre.next = cur;
cur = next;
}
head.next = end;
return head;
}
有朋友可能会说为什么不边走边reverse,这样可以省一个pass。但是问题是这个题目的要求中最后如果不足k个不需要reverse,所以没法边走边倒。这道题考查的还是链表的基本操作,其中reverse是一个非常重要的链表操作,大家要多练习,尽量做到一遍做对无bug。
分享到:
相关推荐
Reverse words in a string-leetcode
第四章 Leetcode 题解 1. Two Sum 2. Add Two Numbers 3. Longest Substring Without Repeating Characters 4. Median of Two Sorted Arrays 7. Reverse Integer ...25. Reverse Nodes in k-Group 26. Remove Dupli
reverse-nodes-in-k-group: 解析 pre_for_next 到辅助函数 29:除以两个整数:溢出; 两反 31:下一个排列:再做一次(排序!) 32:最长有效(),使用栈,左推idx 33: search-in-rotated-sorted-array ,比较中间值...
多线程 leetcode 前言 每天刷点leetcode,基于java语言实现。 leetcode上难度分三档:easy,medium,hard. 如下: easy medium Remove Nth ...Nodes in ...k ...Reverse Nodes in k-Group Trapping Rain Water
lru缓存leetcode leetcode 1. Two Sum 2. Add Two Numbers 3. Longest ...Reverse ...Reverse Nodes in k-Group 26. Remove Duplicates from Sorted Array 27. Remove Element 28. Implement strStr() 3
leetcode 第321题Reversed_Integer Java中的LeetCode逆整数问题解决方案 问题 - 给定一个有符号的 32 位整数 x,返回 x 其数字颠倒。 如果反转 x 导致值超出有符号的 32 位整数范围 [-231, 231 - 1],则返回 0。 ...
字符串可能的余数LeetCode-7-Reverse-An-Integer 我对 LeetCode #7 的解决方案 我处理这个问题的目的是优化时间复杂度而不是空间复杂度。 因此,我避免了通用方法链接解决方案,在这种解决方案中,输入被转换为字符...
leetcode 不会 Leetcode Solutions in Java Linked List Linked List Cycle Given a linked list, determine if it has a cycle in it. public static boolean hasCycle(ListNode head) 快慢指针法,块指针从head....
Reverse-Linked-List-II 要点: - 确定边界条件,定位到起点 - 再利用头插法对指定段的链表逆序 链表逆序之头插法,关键代码(牢记): pre.next = cur.next; cur.next = head.next; head.next = cur; ...
92.reverse-linked-list-ii (反转链表 II) 94.binary-tree-inorder-traversal (二叉树的中序遍历) 101.symmetric-tree (对称二叉树) 102.binary-tree-level-order-traversal (二叉树的层序遍历) 104.maximum-depth-...
leetcode添加元素使和等于 总结 按照类别分类来刷 刷当前题的时候,看下『题目描述』最底下有个『相似题目』,这些题的思路大致也相当 ...reverse-nodes-in-k-group 二叉树 实现一个二叉树 二叉树二叉树的
leetcode盒子嵌套 leetcode-text 92.Reverse Linked List II Runtime: 4 ms, faster than 67.04% of C online submissions for Reverse Linked List II. Memory Usage: 6.9 MB, less than 100.00% of C online ...
190 | [Reverse Bits](https://leetcode.com/problems/reverse-bits/) | [C++](./C++/reverse-bits.cpp) [Python](./Python/reverse-bits.py) | _O(1)_ | _O(1)_ | Easy ||| 191 |[Number of 1 Bits]...
c++ 的array源码分析和reverse-iterator和-Array-const-iterator类
leetcode算法题主函数如何写 Leetcode-Python 参考官方文档: Lession 1: Variable & Control flow 基础语法: Fizz Buzz Reverse 3-digit Integer int变量: a = 1, a = b = c = 1, a = b = c = 1, 100, "linpz" ...
反转 UTF-16 字符串 优化的 UTF-16 兼容反向字符串算法。 它只需要遍历给定字符串的 1/2,并处理 UTF-16 代理对。用法 var reverse = require ( 'reverse-utf16-string' ) ;var reversed = reverse ( 'ab
判断链表是否为回文链表 ...)=k,其中k=1到numOfRows当k>=numOfRows时,对应中间的元素,存储位置应该是(numOfRows-1)-(i-(numOfRows-1)) #longest common prefix 最长的公共前缀长度不会超过列表中最短的字符
reverse-engineering-the-hacker-news-ranking-algorithm, 历史黑客新闻数据的分析与排序算法 反向工程黑客新闻排名算法这个知识库是文章反向工程的一个同伴,它黑客新闻排名算法。 本文探讨了如何利用历史数据来...
leetcode 答案 leetcode-cpp Leetcode Practice with C++ Directory Thanks to 用了这玩意儿贼爽贼带感, 刷题就像是飞的感觉。 With vscode-leetcode, you can fuck leetcode easily. 还有各位discuss tab下面的大佬...
刷leetcode不用stl 3-leetcode-everyday 是时候拼一把了!!! DAY 1 1、two-sum 能同时获取元素和index的方法是使用enumerate() 思路:从第一个元素开始,遍历,求每个位置上的差值保存到dict中,如果在接下来的...