基于百度地图的网站开发,wordpress 程序更新,网络营销方式内容角度,广东省建设执业资格注册中心官方网站K 个一组翻转链表
给你链表的头节点 head #xff0c;每 k 个节点一组进行翻转#xff0c;请你返回修改后的链表。
k 是一个正整数#xff0c;它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍#xff0c;那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改…K 个一组翻转链表
给你链表的头节点 head 每 k 个节点一组进行翻转请你返回修改后的链表。
k 是一个正整数它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值而是需要实际进行节点交换。
方法一将链表先变成List数组List数组按K大小分成n块有余数就为第n1块每块翻转第n1块不翻转然后组成一个新的List数组在按照新的list数组拼接成新的链表返回
时间复杂度On 空间复杂度On (比较好理解的做出来)
package TOP21_30;import Util.ListNode;import java.util.ArrayList;
import java.util.List;//K 个一组翻转链表
//给你链表的头节点 head 每 k 个节点一组进行翻转请你返回修改后的链表。
//k 是一个正整数它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍那么请将最后剩余的节点保持原有顺序。
//你不能只是单纯的改变节点内部的值而是需要实际进行节点交换。
public class Top29 {public static ListNode reverseKGroup(ListNode head, int k) {if (head null || k 1) {return head;}ListInteger list new ArrayList();ListInteger resutlist new ArrayList();while (head ! null) {list.add(head.val);head head.next;}int length list.size();// 因为klengthint n length / k;int t length % k;for (int i 0; i n; i) {ListInteger tempList new ArrayList();for (int j 0; j k; j) {tempList.add(list.get(i * k j));}resutlist.addAll(reverseList(tempList));}if (t ! 0) {ListInteger tempList new ArrayList();for (int i n * k; i length - 1; i) {tempList.add(list.get(i));}resutlist.addAll(tempList);}ListNode node setNodes(0, resutlist);return node;}public static ListNode setNodes(int index, ListInteger nums) {ListNode res new ListNode();res.val nums.get(index);if (index nums.size() - 1) {res.next null;return res;} else {res.next setNodes(index 1, nums);}return res;}private static ListInteger reverseList(ListInteger reverseData) {ListInteger arrayList new ArrayList();for (int i reverseData.size() - 1; i 0; i--) {arrayList.add(reverseData.get(i));}return arrayList;}public static void main(String[] args) {int[] nums {1,2,3,4,5,6,7,8,9,0};ListNode node ListNode.setNodes(0,nums);ListNode node2 reverseKGroup(node,3);ListNode.printListData(node2);}
}方法二递归 Java
解题思路 大致过程可以分解为 1、找到待翻转的k个节点注意若剩余数量小于 k 的话则不需要反转因此直接返回待翻转部分的头结点即可。 2、对其进行翻转。并返回翻转后的头结点注意翻转为左闭又开区间所以本轮操作的尾结点其实就是下一轮操作的头结点。 3、对下一轮 k 个节点也进行翻转操作。 4、将上一轮翻转后的尾结点指向下一轮翻转后的头节点即将每一轮翻转的k的节点连接起来。
具体过程看下图。 //递归方法public static ListNode reverseKGroup2(ListNode head, int k) {//退出递归的条件if(head null ) return head;ListNode tail head;for(int i 0;ik;i){// if(tail null) break; // 这个是不足k也反转if(tail null) return head; // 不足k的节点保持原来顺序tail tail.next;}//反转前k个节点ListNode newHead reverse(head, tail);//下一轮的开始还是tail节点因为你是要确定下一次返回链表的头节点的位置head.next reverseKGroup(tail,k);return newHead;}public static ListNode reverse(ListNode head, ListNode tail){ListNode prev null;ListNode cur head;//只需要把原来判断尾节点为空的改为在传入节点就行。while(cur !tail){ListNode next cur.next;cur.next prev;prev cur;cur next;}return prev;}
完整可执行代码
harryptter / LeetcodeTop100 · GitCode
