• 欢迎来到莫知我哀的博客,日常不定时更新C++、C#、Unity、OpenGL、游戏开发相关文章。同步博客: CSDN
  • 网站左下角可以开启好听的背景音乐~~
  • 如果您觉得本博客很有看点,那么赶紧使用Ctrl+D 收藏吧

[LeetCode] 25. Reverse Nodes in k-Group

算法练习 wahh 147次浏览 0个评论 扫描二维码

题目

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:

  • Your algorithm should use only constant extra space.
  • You may not modify the values in the list's nodes, only nodes itself may be changed.

 

原题链接:https://leetcode.com/problems/reverse-nodes-in-k-group/description/

 

题意

输入一个链表和一个K值,翻转相邻K个位置的节点。如果链表长度不为K的整数倍,那么链表尾端剩余节点不进行翻转变化。注意:程序额外使用的空间必须在常数级,不能交换节点值,只能交换节点。

 

分析

当K=2时,问题等同于LeetCode.24。

使用递归方法每次翻转K个,首先统计剩余节点是否大于等于K;

当大于等于K的时候,使用尾插法对链表前K个节点进行翻转,然后递归处理剩下的节点。

注意:节点间的链接!

空间复杂度O(1),时间复杂度O(n)

 

代码

 


莫知我哀 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:[LeetCode] 25. Reverse Nodes in k-Group
喜欢 (1)
发表我的评论
取消评论
表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
Title - Artist
0:00