给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。
k 是一个正整数,它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。
示例:
给你这个链表:1->2->3->4->5
当 k = 2 时,应当返回: 2->1->4->3->5
当 k = 3 时,应当返回: 3->2->1->4->5
说明:
你的算法只能使用常数的额外空间。 你不能只是单纯的改变节点内部的值,而是需要实际进行节点交换。
原文链接:https://leetcode-cn.com/problems/reverse-nodes-in-k-group
1、找到待翻转的k个节点,若剩余数量小于 k 的话,则不需要反转,因此直接返回待翻转部分的头结点即可。 2、对其进行翻转。并返回翻转后的头结点,翻转为左闭右开区间,所以本轮操作的尾结点其实就是下一轮操作的头结点。 3、对下一轮 k 个节点也进行翻转操作。 4、将上一轮翻转后的尾结点指向下一轮翻转后的头节点,即将每一轮翻转的k的节点连接起来。
大致流程入下图:
head = tail 返回pre节点,也就是值为3的节点作为newHead 。再次递归即可。
public class SwapKGroup { public static ListNode reverseKGroup(ListNode head, int k) { if (head == null || head.next == null) { return head; } ListNode tail = head; for (int i = 0; i < k; i++) { //剩余数量小于k的话,则不需要反转。 if (tail == null) { return head; } tail = tail.next; } // 反转前 k 个元素 ListNode newHead = reverse(head, tail); //下一轮的开始的地方就是tail head.next = reverseKGroup(tail, k); return newHead; } /* 左闭右开区间 */ private static ListNode reverse(ListNode head, ListNode tail) { ListNode pre = null; ListNode next = null; while (head != tail) { next = head.next; head.next = pre; pre = head; head = next; } return pre; } public static void main(String[] args) { ListNode listNode1 = new ListNode(1); ListNode listNode2 = new ListNode(2); ListNode listNode3 = new ListNode(3); ListNode listNode4 = new ListNode(4); listNode1.next = listNode2; listNode2.next = listNode3; listNode3.next = listNode4; listNode4.next = new ListNode(5); reverseKGroup(listNode1,3); } }
本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。
我来说两句