6c4c338ff647d3e237078eae9f091b53
(难度Hard)Problem 25. Reverse Nodes in k-Group(翻转链表中相邻k个元素)

链接

Reverse Nodes in k-Group - LeetCode

难度等级

Hard

题干

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.

Note:

Only constant extra memory is allowed.

You may not alter the values in the list's nodes, only nodes itself may be changed.

题意

给定一个链表和一个数字k,要求返回一个链表。使得链表当中每k个元素倒叙。

注意:

  1. 只能允许线性的额外空间,即是空间复杂度必须在$O(n)$
  2. 不能修改node的值,只能修改node

样例

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

题解

这又是一道名不副实的题,看着Hard难度很唬人,但我觉得其实顶多只能算是Medium。

直接思考如何翻转链表当中的k个相邻的元素可能比较困难,但是我们直接根据要求重新创造一个满足要求的链表则要简单许多。和24题当中的方法其实一样,我们只需要在遍历的时候记录下这k个元素,然后倒叙填入新的链表当中,最后返回即可。

对于这中间需要暂时存储的k个元素,比较容易想到的就是使用vector(java里的arraylist)等数据结构。

如果不考虑链表操作自带的复杂度,这道题几乎没有太多的难度。

top Created with Sketch.