25. K 个一组翻转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例：

给你这个链表：1->2->3->4->5

当 k = 2 时，应当返回: 2->1->4->3->5

当 k = 3 时，应当返回: 3->2->1->4->5

说明：

你的算法只能使用常数的额外空间。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

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.

解题思路

1.分组反转链表操作
2.边界处理

代码

class Solution {     fun reverseKGroup(head: ListNode?, k: Int): ListNode? {         if (head?.next == null) {             return head          }          // 找到tail的地址         var tail = head         for (i in 0..(k - 1)) {             // 当这一组链表节点数小于k,直接返回             if (tail == null) {                 return head             }             // 指针逐一后移,一直移到k-1位置=tail             tail = tail.next         }          // 反转该组         var newHead = reverse(head, tail)          // head.next = 下一组的 newHead         head.next = reverseKGroup(tail, k)          // 返回当前组的newHead         return newHead     }       fun reverse(head: ListNode?, tail: ListNode?): ListNode? {         var cur = head         // cur pre         var pre: ListNode? = null         // cur next         var next: ListNode?          // cur->cur.next         while (cur != tail) {             // next持有cur的next节点             next = cur?.next             // 反转cur节点的next为pre             cur?.next = pre             // 指针向后移到下一个节点             pre = cur             cur = next         }         // 返回newHead         return pre     }  }    class ListNode(var value: Int) {     var next: ListNode? = null     override fun toString(): String {         return "ListNode(value=$value, next=$next)"     } }   

测试函数:

fun main() {     run {         val listNode1 = ListNode(1)         val listNode2 = ListNode(2)         val listNode3 = ListNode(3)         val listNode4 = ListNode(4)         val listNode5 = ListNode(5)         listNode1.next = listNode2         listNode2.next = listNode3         listNode3.next = listNode4         listNode4.next = listNode5         listNode5.next = null         val ans = reverseKGroup(listNode1, 2)         println(ans)     }      run {         val listNode1 = ListNode(1)         val listNode2 = ListNode(2)         val listNode3 = ListNode(3)         val listNode4 = ListNode(4)         val listNode5 = ListNode(5)         listNode1.next = listNode2         listNode2.next = listNode3         listNode3.next = listNode4         listNode4.next = listNode5         listNode5.next = null         val ans = reverseKGroup(listNode1, 3)         println(ans)     }  } 

输出:

ListNode(value=2, next=ListNode(value=1, next=ListNode(value=4, next=ListNode(value=3, next=ListNode(value=5, next=null)))))
ListNode(value=3, next=ListNode(value=2, next=ListNode(value=1, next=ListNode(value=4, next=ListNode(value=5, next=null)))))

相似的题型

反转链表

Reverse a singly linked list.
Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?
https://leetcode-cn.com/explore/interview/card/bytedance/244/linked-list-and-tree/1038/

源代码:

/**  * Example:  * var li = ListNode(5)  * var v = li.`val`  * Definition for singly-linked list.  * class ListNode(var `val`: Int) {  *     var next: ListNode? = null  * }  */ class Solution {     fun reverseList(head: ListNode?): ListNode? {         var cur = head         var pre:ListNode? = null         var next:ListNode? = null                  while(cur!=null){             next = cur.next             cur.next = pre             pre = cur             cur = next         }                  return pre      } } 

参考资料

https://leetcode-cn.com/problems/reverse-nodes-in-k-group/
https://leetcode-cn.com/submissions/detail/67275479/

Kotlin开发者社区

专注 Java、 Kotlin、Spring/Spring Boot、MySQL、redis、neo4j、NoSQL、Android、JavaScript、React、Node、函数式编程、编程思想、”高可用，高性能，高实时”大型分布式系统架构设计主题。

High availability, high performance, high real-time large-scale distributed system architecture design。

分布式框架：Zookeeper、分布式中间件框架等
分布式存储：GridFS、FastDFS、TFS、MemCache、redis等
分布式数据库：Cobar、tddl、Amoeba、Mycat
云计算、大数据、AI算法
虚拟化、云原生技术
分布式计算框架：MapReduce、Hadoop、Storm、Flink等
分布式通信机制：Dubbo、RPC调用、共享远程数据、消息队列等
消息队列MQ：Kafka、MetaQ，RocketMQ
怎样打造高可用系统：基于硬件、软件中间件、系统架构等一些典型方案的实现：HAProxy、基于Corosync+Pacemaker的高可用集群套件中间件系统
Mycat架构分布式演进
大数据Join背后的难题：数据、网络、内存和计算能力的矛盾和调和
Java分布式系统中的高性能难题：AIO，NIO，Netty还是自己开发框架？
高性能事件派发机制：线程池模型、Disruptor模型等等。。。

合抱之木，生于毫末；九层之台，起于垒土；千里之行，始于足下。不积跬步，无以至千里；不积小流，无以成江河。