沧州商城网站开发设计,开个网站做代理赚钱吗,flash制作网站的好处,建德网站文章目录 题目与变形解法 题目与变形
字节一面中关于 K个一组链表反转 的题目变形。
K个一组链表反转。K个一组链表反转#xff0c;链表尾不足K个的元素也需要反转。K个一组链表反转#xff0c;但是从链表尾部开始反转。反转从位置 left 到位置 right 的链表节点
解法
四… 文章目录 题目与变形解法 题目与变形
字节一面中关于 K个一组链表反转 的题目变形。
K个一组链表反转。K个一组链表反转链表尾不足K个的元素也需要反转。K个一组链表反转但是从链表尾部开始反转。反转从位置 left 到位置 right 的链表节点
解法
四个算法万变不离其宗主要掌握原题即可。
public class No0025ReverseGroup2 {public static void main(String[] args) {int[] array {1, 2, 3, 4, 5, 6, 7, 8};int k 3;No0025ReverseGroup2 demo new No0025ReverseGroup2();ListNode node ListNode.createListNode(array);System.out.println(原始节点: node);ListNode res demo.reverseKGroup(node, k);System.out.println(K个一组反转: res);ListNode res2 demo.reverseKGroup2(ListNode.createListNode(array), k);System.out.println(剩余不足也K个反转: res2);ListNode res3 demo.reverseKGroup3(ListNode.createListNode(array), k);System.out.println(从尾部开始K个一组反转: res3);ListNode res4 demo.reverseKGroup4(ListNode.createListNode(array), 3, 6);System.out.println(反转指定区域的链表: res4);}/*** 反转 left 到 right 位置的元素*/private ListNode reverseKGroup4(ListNode listNode, int begin, int stop) {ListNode result new ListNode();result.next listNode;ListNode left result;ListNode right result;for (int i 0; i stop; i) {if (i begin - 1) {// 保持 left.next 指向反转的起始节点left left.next;}right right.next;}while (left.next ! right) {// 理解这里就OK了ListNode curr left.next;left.next curr.next;curr.next right.next;right.next curr;}return result.next;}/*** 变形2从链表尾部开始 k 个一组反转*/private ListNode reverseKGroup3(ListNode listNode, int k) {int count 0;ListNode countNode listNode;while (Objects.nonNull(countNode)) {countNode countNode.next;count;}ListNode result new ListNode(0);result.next listNode;ListNode left result;ListNode right result;int beginIndex count % 3;for (int i 0; i beginIndex; i) {left left.next;right right.next;}while (true) {for (int i 0; i k Objects.nonNull(right); i) {right right.next;}if (Objects.isNull(right)) {break;}ListNode leftPtr left.next;while (left.next ! right) {// 理解这里就OK了ListNode curr left.next;left.next curr.next;curr.next right.next;right.next curr;}left leftPtr;right leftPtr;}return result.next;}/*** 变形1剩余元素不足K个也需要反转*/private ListNode reverseKGroup2(ListNode listNode, int k) {ListNode result new ListNode(0);result.next listNode;ListNode left result;ListNode right result;ListNode preRight right;while (true) {for (int i 0; i k Objects.nonNull(right); i) {preRight right;right right.next;}if (Objects.isNull(right)) {// 处理剩余部分的反转ListNode curr left.next;left.next curr.next;curr.next preRight.next;preRight.next curr;break;}ListNode leftPtr left.next;while (left.next ! right) {// 理解这里就OK了ListNode curr left.next;left.next curr.next;curr.next right.next;right.next curr;}left leftPtr;right leftPtr;}return result.next;}/*** 原题K个一组反转*/private ListNode reverseKGroup(ListNode listNode, int k) {ListNode result new ListNode(0);result.next listNode;ListNode left result;ListNode right result;while (true) {for (int i 0; i k Objects.nonNull(right); i) {right right.next;}if (Objects.isNull(right)) {break;}ListNode leftPtr left.next;while (left.next ! right) {// 理解这里就OK了ListNode curr left.next;left.next curr.next;curr.next right.next;right.next curr;}left leftPtr;right leftPtr;}return result.next;}
}// 补充自用节点类
public class ListNode {public int val;public ListNode next;public ListNode() {}public ListNode(int val) {this.val val;}public ListNode(int val, ListNode next) {this.val val;this.next next;}public static ListNode createListNode(int[] array) {ListNode head new ListNode(array[0]);ListNode node head;for (int i 1; i array.length; i) {ListNode next new ListNode(array[i]);node.next next;node next;}return head;}
}
