字节算法-链表翻转与变形

题目与变形

字节一面中关于 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;}
}