新博文地址:
[leetcode]Reverse Nodes in k-Group
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.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For 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
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For 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
跟这道题很像,只不过加了一个迭代的要求,很直接的想法:
1.算出需要转置区间的个数
2.对每一次转置区间找到其前驱和后驱
3.对每个转置区间进行转置
其实,找前驱和后驱的代码是可以优化的,留在第二遍再优化,而且这样写虽然代码不够简洁,但是可读性稍稍好一些。
public ListNode reverseKGroup(ListNode head, int k) { int length = getLength(head); if(length < k || k <= 1){ return head; } ListNode hhead = new ListNode(0); hhead.next = head; for(int i = 0; i < length / k; i++){ ListNode pre = getStartInLoopN(hhead, i, k); ListNode post = getEndInLoopN(pre, k); ListNode iPre = pre; ListNode iNode = pre.next; ListNode iPost = iNode.next; while(iNode != post){ if(iNode == pre.next){ iNode.next = post; iPre = iNode; iNode = iPost; iPost = iNode.next; }else if(iNode.next == post){ pre.next = iNode; iNode.next = iPre; iNode = post; }else{ iNode.next = iPre; iPre = iNode; iNode = iPost; iPost = iNode.next; } } } return hhead.next; } private ListNode getStartInLoopN(ListNode hhead,int n,int k){ for(int i = 0 ; i < n*k; i++){ hhead = hhead.next; } return hhead; } private ListNode getEndInLoopN(ListNode startNode,int k){ for(int i = 0 ; i < k + 1; i++){ startNode = startNode.next; } return startNode; } private int getLength(ListNode head){ int count = 0; while(head != null){ head = head.next; count++; } return count ; }
相关推荐
LeetCode-Solutions-in-Swift.zip,swift 5中的leetcode解决方案
leetcode 答案解析 golang解答
示例输入:输出: 1->1->2->3->4->4->5->6解题思路将k个链表建立成一个最小堆,再从堆顶pop()出每一个元素,连接成链表heapq是pyth
解题思路思路和LeetCode-python 503.下一个更大元素 II一致,只是这里求的是下标的距离,而不是数值倒序搜索,用到栈,栈里存储索引情况1:若栈为
解题思路如果最后剩下1-3个石头,你肯定是赢家,如果此时剩下4个石头,你无论拿多少个,对方一定会赢。如果此时剩下5个石头,这时你的最佳策略是拿走一个石头,这是对
示例1输出:"1[.]1[.]1[.]1"示例2输出:"255[.]100[.]50[.]0"代码实现本文链接:
令 dp(i, j) 为亚历克斯可以获得的最大分数,其中剩下的堆中的石子数是 piles[i], piles[i+1], ..., piles[j]。我们可以根
示例1输入:[[1,0,1],[0,0,0],[1,0,1]]输出:2解释:海洋区域 (1, 1) 和所有陆地区域之间的距离都达到最大,最大距离为 2。解题思路
要考虑第一个节点要被删除的情况代码实现self.next = Nonedef removeElements(self, head: ListNode, val:
给定一个链表,返回链表开始入环的第一个节点。如果链表无环,则返回 null。为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从
示例// 返回 1// 该操作会使得密钥 2 作废// 返回 -1 (未找到)// 该操作会使得密钥 1 作废// 返回 -1 (未找到)// 返回 3// 返
示例1输入: 1 1**示例2**输入: 1 1代码实现Definition for a binary tree node.本文链接: https://www.
示例1输出:[0,2,1,-6,6,-7,9,1,2,0,1]解释:0 + 2 + 1 = -6 + 6 - 7 + 9 + 1 = 2 + 0 + 1示例2输
示例1输入: 1->1->2输出: 1->2示例2输入: 1->1->2->3->3输出: 1->2->3解题思路如果当前节点的值和下一个节点的值相等,则当前节
示例解题思路最大的深度是左子树或右子树中深度中更大的一个+1,递归的在子树的子树中寻找代码实现Definition for a binary tree node
题目链接难度:简单 类型: 数组、二分法我们把符合下列属性的数组 A 称作山脉:给定一个确定为山脉的数组,返回任何满足 A[0] [1]
第一插:[[7,0]] 第二插:[[7,0], [7,1]] 第三插:[[7,0], [6,1],[7,1]] 第四插:[[5,0],[7,0], [6,1],
示例1输入:[3,2,1]输出:[3,1,2]解释:交换 2 和 1示例2输入:[1,1,5]输出:[1,1,5]解释: 这已经是最小排列示例3输入:[1,9,
1.去除字符串头尾空格 2.判断符号 3.提取出数字字符直到第一个不为数字的字符 4.字符串转整数,乘以符号 4.判断是否超出整数范围,并返回相应的值
Algorithm-LeetCode-Solution-From-GuaZiDou.zip,Leetcode解决方案Gitbook,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。